Další formáty:
BibTeX
LaTeX
RIS
@proceedings{759246, author = {Hliněný, Petr and Oum, Sang il}, booktitle = {Joint Meeting of the AMS - NZMS 2007}, keywords = {matroid; branch-width; parametrized algorithm}, language = {eng}, title = {Finding Branch-decompositions and Rank-decompositions}, url = {http://www.mcs.vuw.ac.nz/~mathmeet/amsnzms2007/}, year = {2007} }
TY - CONF ID - 759246 AU - Hliněný, Petr - Oum, Sang il PY - 2007 TI - Finding Branch-decompositions and Rank-decompositions KW - matroid KW - branch-width KW - parametrized algorithm UR - http://www.mcs.vuw.ac.nz/~mathmeet/amsnzms2007/ 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(n3) 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-decompositions and Rank-decompositions. In \textit{Joint Meeting of the AMS - NZMS 2007}. 2007.
|