Minimal interval completion through graph exploration

DOI10.1016/j.tcs.2008.09.053zbMath1161.05052WikidataQ62046056 ScholiaQ62046056MaRDI QIDQ1001896

Karol Suchan, Ioan Todinca

Publication date: 19 February 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.09.053

zbMATH Keywords

interval graph; minimal 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.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal greedy heuristic to color interval graphs
• On minimal augmentation of a graph to obtain an interval graph
• On the pathwidth of chordal graphs
• Separability generalizes Dirac's theorem
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Minimal comparability completions of arbitrary graphs
• Minimal Proper Interval Completions
• Minimal Split Completions of Graphs
• PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
• Treewidth: Structure and Algorithms
• Algorithms – ESA 2005
• A Characterization of Comparability Graphs and of Interval Graphs