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.
|
