Minimal proper interval completions

DOI10.1016/j.ipl.2007.11.013zbMath1185.05107OpenAlexW2159194941WikidataQ62046062 ScholiaQ62046062MaRDI QIDQ963366

Ivan Rapaport, Ioan Todinca, Karol Suchan

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.11.013

zbMATH Keywords

bandwidthgraph algorithmsproper interval graphsminimal proper interval completions

Mathematics Subject Classification ID

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

Related Items (6)

Linear-time minimal cograph editing ⋮ An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ An \(O(n^2)\) time algorithm for the minimal permutation completion problem ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem

Cites Work

• Unnamed Item
• Minimal fill in O(\(n^{2.69}\)) time
• A linear time recognition algorithm for proper interval graphs
• Separability generalizes Dirac's theorem
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Algorithmic graph theory and perfect graphs
• Betweenness, orders and interval graphs
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Minimal Split Completions of Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
• Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Algorithms – ESA 2005

This page was built for publication: Minimal proper interval completions