Characterizing and Computing Minimal Cograph Completions
From MaRDI portal
Publication:3507328
DOI10.1007/978-3-540-69311-6_17zbMath1143.68506OpenAlexW1770499284MaRDI QIDQ3507328
Daniel Lokshtanov, Charis Papadopoulos, Federico Mancini
Publication date: 19 June 2008
Published in: Frontiers in Algorithmics (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.144.346
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone, Strongly chordal and chordal bipartite graphs are sandwich monotone, Characterizing and computing minimal cograph completions, Dynamically maintaining split graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A vertex incremental approach for maintaining chordality
- Safe separators for treewidth
- 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 practical algorithm for making filled graphs minimal
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Error compensation in leaf power problems
- NP-completeness results for edge modification problems
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- 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
- Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions
- 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
- Complexity classification of some edge modification problems
