Interval Completion Is Fixed Parameter Tractable

DOI10.1137/070710913zbMath1227.05241WikidataQ56267431 ScholiaQ56267431MaRDI QIDQ3642873

Christophe Paul, Pinar Heggernes, Jan Arne Telle, Yngve Villanger

Publication date: 6 November 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

branching; interval graphs; FPT algorithm; profile minimization; edge completion

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

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

05C85: Graph algorithms (graph-theoretic aspects)