Minimal interval completion through graph exploration
From MaRDI portal
Publication:1001896
DOI10.1016/j.tcs.2008.09.053zbMath1161.05052WikidataQ62046056 ScholiaQ62046056MaRDI QIDQ1001896
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
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