Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems
From MaRDI portal
Publication:4575659
DOI10.1137/1.9781611974331.ch79zbMath1410.68281arXiv1508.05282OpenAlexW2228247117MaRDI QIDQ4575659
Paweł Komosa, Lukáš Mach, Michał Pilipczuk, Marek Cygan, Ivan A. Bliznets
Publication date: 16 July 2018
Published in: ACM Transactions on Algorithms, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1508.05282
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Completion to chordal distance-hereditary graphs: a quartic vertex-kernel, A survey of parameterized algorithms and the complexity of edge modification, Algorithms for automatic ranking of participants and tasks in an anonymized contest, Rank reduction of oriented graphs by vertex and edge deletions, Minimum fill-in: inapproximability and almost tight lower bounds, Unnamed Item, (Sub)linear kernels for edge modification problems toward structured graph classes