A Subexponential Parameterized Algorithm for Proper Interval Completion

DOI10.1137/140988565zbMath1330.68102WikidataQ60488386 ScholiaQ60488386MaRDI QIDQ5899484

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

Publication date: 30 October 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/140988565

zbMATH Keywords

fixed-parameter tractability; subexponential algorithm; proper interval graphs; proper interval completion

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

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