Characterizing and computing minimal cograph completions
From MaRDI portal
Publication:972335
DOI10.1016/j.dam.2009.01.016zbMath1216.05158OpenAlexW2089334106MaRDI QIDQ972335
Federico Mancini, Daniel Lokshtanov, Charis Papadopoulos
Publication date: 25 May 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2009.01.016
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (7)
On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ Linear-time minimal cograph editing ⋮ BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes ⋮ 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A vertex incremental approach for maintaining chordality
- Safe separators for treewidth
- Dynamically maintaining split graphs
- Complement reducible graphs
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- A practical algorithm for making filled graphs minimal
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Minimal comparability completions of arbitrary graphs
- Error compensation in leaf power problems
- NP-completeness results for edge modification problems
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- Characterizing and Computing Minimal Cograph Completions
- Minimal Proper Interval Completions
- Minimal Split Completions of Graphs
- Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
- Characterizing Minimal Interval Completions
- Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions
- Interval Completion Is Fixed Parameter Tractable
- A Linear Recognition Algorithm for Cographs
- The complexity of some edge deletion problems
- Computing the Minimum Fill-In is NP-Complete
- Minimum Fill-in on Circle and Circular-Arc Graphs
- Treewidth and Minimum Fill-in on d-Trapezoid Graphs
- Graph Classes: A Survey
- Graph Sandwich Problems
- Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
- Minimal Interval Completion Through Graph Exploration
- Automata, Languages and Programming
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Complexity classification of some edge modification problems
This page was built for publication: Characterizing and computing minimal cograph completions
