Minimal split completions

DOI10.1016/j.dam.2008.08.010zbMath1211.05136MaRDI 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 algorithms; split graphs; graph classes; minimal split completion

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C76: Graph operations (line graphs, products, etc.)

Related Items

Faster and enhanced inclusion-minimal cograph completion, Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes, An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem, Strongly chordal and chordal bipartite graphs are sandwich monotone, An \(O(n^2)\) time algorithm for the minimal permutation completion problem, Linear-time minimal cograph editing, Recognition of split-graphic sequences, Faster parameterized algorithms for deletion to split graphs, An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem, An integer programming model for the Minimum Interval Graph Completion Problem

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