Faster and enhanced inclusion-minimal cograph completion

DOI10.1007/978-3-319-71150-8_19zbMath1470.05155arXiv2001.07765OpenAlexW3084120519MaRDI QIDQ5915859

Daniel Lokshtanov, Éric Thierry, Thi Ha Duong Phan, Christophe Crespelle

Publication date: 26 February 2018

Published in: Discrete Applied Mathematics, Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2001.07765

zbMATH Keywords

cographedge modificationminimal completion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ Linear-time minimal cograph editing ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
• Complexity and parameterized algorithms for cograph editing
• Treewidth and minimum fill-in on permutation graphs in linear time
• Safe separators for treewidth
• On miniaturized problems in parameterized complexity theory
• Testing branch-width
• Minimal proper interval completions
• Minimal split completions
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
• Characterizing and computing minimal cograph completions
• Eigenvalues and expanders
• Complement reducible graphs
• On minimal augmentation of a graph to obtain an interval graph
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Efficient graph representations
• A practical algorithm for making filled graphs minimal
• A data structure for dynamic trees
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• On the threshold of intractability
• Minimal comparability completions of arbitrary graphs
• Approximating clique-width and branch-width
• Error compensation in leaf power problems
• Fully dynamic recognition algorithm and certificate for directed cographs
• Incidence matrices, interval graphs and seriation in archeology
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem
• Defining and identifying cograph communities in complex networks
• Fast Quasi-Threshold Editing
• Expander graphs and their applications
• Interval Completion Is Fixed Parameter Tractable
• A Linear Recognition Algorithm for Cographs
• Complexity of Finding Embeddings in a k-Tree
• Minimum Fill-in on Circle and Circular-Arc Graphs
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Graph Classes: A Survey
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• Mapping the genome
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Faster and enhanced inclusion-minimal cograph completion