Subexponential Parameterized Algorithm for I <scp>nterval</scp> C <scp>ompletion</scp>

DOI10.1145/3186896zbMath1454.68094MaRDI QIDQ4554363

Marcin Pilipczuk, Fedor V. Fomin, Michał Pilipczuk, Ivan A. Bliznets

Publication date: 13 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3186896

zbMATH Keywords

interval graphs; completion problems; graph modification problems; subexponential algorithms

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)

68Q27: Parameterized complexity, tractability and kernelization