Characterizing Minimal Interval Completions

DOI10.1007/978-3-540-70918-3_21MaRDI QIDQ3590937zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Karol Suchan, Ioan Todinca, 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

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)

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

Cited in

(14)

• Pathwidth is NP-Hard for Weighted Trees
• 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
• Fixed-parameter complexity of minimum profile problems
• Profile minimization on products of graphs
• Characterizing and Computing Minimal Cograph Completions
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• The interval graph completion problem for the complete multipartite graphs
• 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

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)