Minimal interval completion through graph exploration

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

Ioan Todinca, Karol Suchan

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 graphminimal interval completion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (2)

On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem

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

This page was built for publication: Minimal interval completion through graph exploration