Other formats:
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 and Sang-il OUM. Finding branch-decomposition and rank-decomposition (Extended abstract). In \textit{European Symposium on Algorithms (ESA 2007)}. Berlin: Springer Verlag, 2007, p.~163-174. ISBN~978-3-540-75519-7.
|
