Další formáty:
BibTeX
LaTeX
RIS
@article{1480301, author = {Hliněný, Petr}, article_location = {Philadelphia}, article_number = {2}, doi = {http://dx.doi.org/10.1137/17M1120129}, keywords = {matroid; path-width; trellis-width; fixed-parameter tractability; well-quasi-ordering}, language = {eng}, issn = {0895-4801}, journal = {SIAM Journal on Discrete Mathematics}, title = {A Simpler Self-reduction Algorithm for Matroid Path-width}, url = {http://arxiv.org/abs/1605.09520}, volume = {32}, year = {2018} }
TY - JOUR ID - 1480301 AU - Hliněný, Petr PY - 2018 TI - A Simpler Self-reduction Algorithm for Matroid Path-width JF - SIAM Journal on Discrete Mathematics VL - 32 IS - 2 SP - 1425-1440 EP - 1425-1440 PB - SIAM SN - 08954801 KW - matroid KW - path-width KW - trellis-width KW - fixed-parameter tractability KW - well-quasi-ordering UR - http://arxiv.org/abs/1605.09520 L2 - http://arxiv.org/abs/1605.09520 N2 - The path-width of matroids naturally generalizes the better known parameter of path-width for graphs and is NP-hard by a reduction from the graph case. While the term matroid path-width was formally introduced in [J. Geelen, B. Gerards, and G. Whittle, J. Combin. Theory Ser. B, 96 (2006), pp. 405-425] in pure matroid theory, it was soon recognized in [N. Kashyap, SIAM J. Discrete Math., 22 (2008), pp. 256-272] that it is the same concept as the long-studied so-called trellis complexity in coding theory, later named trellis-width, and hence it is an interesting notion also from the algorithmic perspective. It follows from a result of Hlineny [P. Hlieny, J. Combin. Theory Ser. B, 96 (2006), pp. 325-351] that the decision problem-whether a given matroid over a finite field has path-width at most t-is fixed-parameter tractable (FPT) in t, but this result does not give any clue about constructing a path-decomposition. The first constructive and rather complicated FPT algorithm for path-width of matroids over a finite field was given in [J. Jeong, E. J. Kim, and S. Oum, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2016, pp. 1695-1704]. Here we propose a simpler "self-reduction" FPT algorithm for a path-decomposition. Precisely, we design an efficient routine that constructs an optimal pathdecomposition of a matroid by calling any subroutine for testing whether the path-width of a matroid is at most t (such as the aforementioned decision algorithm for matroid path-width). ER -
HLINĚNÝ, Petr. A Simpler Self-reduction Algorithm for Matroid Path-width. \textit{SIAM Journal on Discrete Mathematics}. Philadelphia: SIAM, 2018, roč.~32, č.~2, s.~1425-1440. ISSN~0895-4801. Dostupné z: https://dx.doi.org/10.1137/17M1120129.
|