Další formáty:
BibTeX
LaTeX
RIS
@article{587963,
author = {Hliněný, Petr},
article_location = {USA},
article_number = {2},
keywords = {representable matroid; parametrized algorithm; branch-width; rank-width},
language = {eng},
issn = {0097-5397},
journal = {SIAM Journal on Computing},
title = {A Parametrized Algorithm for Matroid Branch-Width},
url = {http://epubs.siam.org/sam-bin/dbq/toc/SICOMP/35/2},
volume = {35},
year = {2005}
}
TY - JOUR
ID - 587963
AU - Hliněný, Petr
PY - 2005
TI - A Parametrized Algorithm for Matroid Branch-Width
JF - SIAM Journal on Computing
VL - 35
IS - 2
SP - 259 - 277
EP - 259 - 277
PB - SIAM
SN - 00975397
KW - representable matroid
KW - parametrized algorithm
KW - branch-width
KW - rank-width
UR - http://epubs.siam.org/sam-bin/dbq/toc/SICOMP/35/2
N2 - Branch-width is a structural parameter very closely related to tree-width, but branchwidth has an immediate generalization from graphs to matroids. We present an algorithm that, for a given matroid M of bounded branch-width t which is represented over a finite field, finds a branch decomposition of M of width at most 3t in cubic time. Then we show that the branch-width of M is a uniformly fixed-parameter tractable problem. Other applications include recognition of matroid properties definable in the monadic second-order logic for bounded branch-width, or [Oum] a cubic time approximation algorithm for graph rank-width and clique-width.
ER -
HLINĚNÝ, Petr. A Parametrized Algorithm for Matroid Branch-Width. \textit{SIAM Journal on Computing}. USA: SIAM, 2005, roč.~35, č.~2, s.~259 - 277. ISSN~0097-5397.
|
