Minimal comparability completions of arbitrary graphs
From MaRDI portal
Publication:2476257
DOI10.1016/j.dam.2007.08.039zbMath1136.05072OpenAlexW2123268636MaRDI QIDQ2476257
Charis Papadopoulos, Federico Mancini, Pinar Heggernes
Publication date: 18 March 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2007.08.039
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (9)
On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ An integer programming model for the Minimum Interval Graph Completion Problem ⋮ Linear-time minimal cograph editing ⋮ An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem ⋮ An \(O(n^2)\) time algorithm for the minimal permutation completion problem ⋮ Characterizing and computing minimal cograph completions ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Minimal interval completion through graph exploration ⋮ An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Orienting graphs to optimize reachability
- A vertex incremental approach for maintaining chordality
- Minimal fill in O(\(n^{2.69}\)) time
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- Minimal Proper Interval Completions
- Minimal Split Completions of Graphs
- On Comparability and Permutation Graphs
- Computing the Minimum Fill-In is NP-Complete
- Algorithmic Aspects of Vertex Elimination on Graphs
- Minimal Interval Completion Through Graph Exploration
- Complexity classification of some edge modification problems
This page was built for publication: Minimal comparability completions of arbitrary graphs
