Minimal split completions

DOI10.1016/j.dam.2008.08.010zbMath1211.05136OpenAlexW2117458675MaRDI QIDQ967310

Pinar Heggernes, Federico Mancini

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.010

zbMATH Keywords

graph algorithmssplit graphsgraph classesminimal split completion

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Related Items

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 ⋮ 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 ⋮ Strongly chordal and chordal bipartite graphs are sandwich monotone ⋮ Recognition of split-graphic sequences ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem ⋮ Faster parameterized algorithms for deletion to split graphs

Cites Work

• Unnamed Item
• Minimal triangulations of graphs: a survey
• Minimal fill in O(\(n^{2.69}\)) time
• The splittance of a graph
• Inheritance principles for chordal graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• A practical algorithm for making filled graphs minimal
• Algorithmic graph theory and perfect graphs
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Characterizing Minimal Interval Completions
• Computing the Minimum Fill-In is NP-Complete
• Algorithmic Aspects of Vertex Elimination on Graphs
• `` Strong NP-Completeness Results
• Several results on chordal bipartite graphs
• Fully dynamic algorithms for chordal graphs and split graphs
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Algorithms – ESA 2005
• Complexity classification of some edge modification problems

This page was built for publication: Minimal split completions