Minimal interval completion through graph exploration

DOI10.1016/J.TCS.2008.09.053MaRDI QIDQ1001896zbMATH OpenOpenAlexDBLPWikidataFDO

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

Mathematics Subject Classification ID

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

Recommendations

• Minimal Interval Completion Through Graph Exploration
• Graph searching and interval completion
• An integer programming model for the minimum interval graph completion problem
• scientific article; zbMATH DE number 1262811
• Algorithms – ESA 2005
• The interval graph completion problem for the complete multipartite graphs
• Optimal constrained graph exploration
• Optimal constrained graph exploration
• On representing an interval graph using the minimum number of interval lengths
• Characterizing and computing minimal cograph completions

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• Algorithms – ESA 2005
• An optimal greedy heuristic to color interval graphs
• Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Minimal Proper Interval Completions
• Minimal Split Completions of Graphs
• Minimal comparability completions of arbitrary graphs
• On minimal augmentation of a graph to obtain an interval graph
• On the pathwidth of chordal graphs
• Partition refinement techniques: an interesting algorithmic tool kit
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Separability generalizes Dirac's theorem
• Treewidth: Structure and Algorithms

Cited in

(9)

• An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
• On the effectiveness of the incremental approach to minimal chordal edge modification
• Minimal Interval Completion Through Graph Exploration
• scientific article; zbMATH DE number 1375600 (Why is no real title available?)
• Algorithms – ESA 2005
• An \({\mathcal{O}}(n^2)\)-time algorithm for the minimal interval completion problem
• Characterizing Minimal Interval Completions
• Minimal Proper Interval Completions
• An integer programming model for the minimum interval graph completion problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1001896)