Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{722630, author = {Hliněný, Petr and Oum, Sangandil}, address = {Berlin}, booktitle = {European Symposium on Algorithms (ESA 2007)}, keywords = {graph; matroid; rank-width; clique-width; branch-width; fixed parameter tractable algorithm}, language = {eng}, location = {Berlin}, isbn = {978-3-540-75519-7}, pages = {163-174}, publisher = {Springer Verlag}, title = {Finding branch-decomposition and rank-decomposition (Extended abstract)}, url = {http://esa-symposium.org/}, year = {2007} }
TY - JOUR ID - 722630 AU - Hliněný, Petr - Oum, Sang-il PY - 2007 TI - Finding branch-decomposition and rank-decomposition (Extended abstract) PB - Springer Verlag CY - Berlin SN - 9783540755197 KW - graph KW - matroid KW - rank-width KW - clique-width KW - branch-width KW - fixed parameter tractable algorithm UR - http://esa-symposium.org/ N2 - We present a new algorithm that can output the rank-decomposition of width at most $k$ of a graph if such exists. For that we use an algorithm that, for an input matroid represented over a fixed finite field, outputs its branch-decomposition of width at most $k$ if such exists. This algorithm works also for partitioned matroids. Both these algorithms are fixed-parameter tractable, that is, they run in time $O(n^3)$ for each fixed value of $k$ where $n$ is the number of vertices / elements of the input. ER -
HLINĚNÝ, Petr a Sang-il OUM. Finding branch-decomposition and rank-decomposition (Extended abstract). In \textit{European Symposium on Algorithms (ESA 2007)}. Berlin: Springer Verlag, 2007, s.~163-174. ISBN~978-3-540-75519-7.
|