Další formáty:
BibTeX
LaTeX
RIS
@article{775814, author = {Hliněný, Petr and Oum, Sangandil}, article_location = {USA}, article_number = {3}, keywords = {graph; matroid; rank-width; clique-width; branch-width; fixed parameter tractable algorithm}, language = {eng}, issn = {0097-5397}, journal = {SIAM Journal on Computing}, title = {Finding branch-decomposition and rank-decomposition}, url = {http://dx.doi.org/10.1137/070685920}, volume = {38}, year = {2008} }
TY - JOUR ID - 775814 AU - Hliněný, Petr - Oum, Sang-il PY - 2008 TI - Finding branch-decomposition and rank-decomposition JF - SIAM Journal on Computing VL - 38 IS - 3 SP - 1012-1032 EP - 1012-1032 PB - SIAM SN - 00975397 KW - graph KW - matroid KW - rank-width KW - clique-width KW - branch-width KW - fixed parameter tractable algorithm UR - http://dx.doi.org/10.1137/070685920 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. \textit{SIAM Journal on Computing}. USA: SIAM, 2008, roč.~38, č.~3, s.~1012-1032. ISSN~0097-5397.
|