Characterizing and computing minimal cograph completions
type: Item
instance of: scholarly article
title: Characterizing and computing minimal cograph completions
zbMATH Open document ID: 1216.05158
author: Daniel Lokshtanov
author: F. Mancini
author: Charis Papadopoulos
published in: Discrete Applied Mathematics
publication date: 2010-05-25T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5711867
zbMATH Keywords: minimal completions
zbMATH Keywords: cographs
zbMATH Keywords: linear-time algorithms
MaRDI profile type: Publication
full work available at URL: j.dam.2009.01.016
OpenAlex ID: W2089334106
cites work: Characterizing and Computing Minimal Cograph Completions
cites work: Complexity classification of some edge modification problems
cites work: Q5683627
cites work: NP-completeness results for edge modification problems
cites work: The complexity of some edge deletion problems
cites work: Computing the Minimum Fill-In is NP-Complete
cites work: Q4542518
cites work: Treewidth and minimum fill-in: Grouping the minimal separators
cites work: Treewidth and Minimum Fill-in on d-Trapezoid Graphs
cites work: Graph-Theoretic Concepts in Computer Science
cites work: On treewidth and minimum fill-in of asteroidal triple-free graphs
cites work: A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
cites work: Minimum Fill-in on Circle and Circular-Arc Graphs
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: Interval Completion Is Fixed Parameter Tractable
cites work: Error compensation in leaf power problems
cites work: Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
cites work: Minimal Split Completions of Graphs
cites work: Minimal comparability completions of arbitrary graphs
cites work: Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions
cites work: Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)
cites work: Minimal Proper Interval Completions
cites work: Minimal Interval Completion Through Graph Exploration
cites work: A practical algorithm for making filled graphs minimal
cites work: Automata, Languages and Programming
cites work: Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
cites work: Safe separators for treewidth
cites work: Dynamically maintaining split graphs
cites work: A Linear Recognition Algorithm for Cographs
cites work: Complement reducible graphs
cites work: Graph Classes: A Survey
cites work: Characterizing Minimal Interval Completions
cites work: Graph Sandwich Problems
cites work: A fully dynamic algorithm for modular decomposition and recognition of cographs.
cites work: Q4091421
cites work: A vertex incremental approach for maintaining chordality
DOI: 10.1016/J.DAM.2009.01.016
description: scientific article; zbMATH DE number 5711867