Characterizing Minimal Interval Completions

DOI10.1007/978-3-540-70918-3_21zbMATH Open1171.68620OpenAlexW1512056994MaRDI QIDQ3590937FDOQ3590937

Pinar Heggernes, Ioan Todinca, Karol Suchan, Yngve Villanger

Publication date: 3 September 2007

Published in: STACS 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70918-3_21

Recommendations

• Algorithms – ESA 2005
• An \({\mathcal{O}}(n^2)\)-time algorithm for the minimal interval completion problem
• Minimal interval completion through graph exploration
• Minimal Interval Completion Through Graph Exploration
• Minimal proper interval completions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (13)

• Pathwidth of Circular-Arc Graphs
• Characterizing and computing minimal cograph completions
• Minimal split completions
• On listing, sampling, and counting the chordal graphs with edge constraints
• Profile minimization on products of graphs
• Fixed-parameter complexity of minimum profile problems
• Characterizing and Computing Minimal Cograph Completions
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• On the proper interval completion problem within some chordal subclasses
• Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
• Strongly chordal and chordal bipartite graphs are sandwich monotone
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Pathwidth is NP-Hard for Weighted Trees

This page was built for publication: Characterizing Minimal Interval Completions

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