Minimal split completions
From MaRDI portal
Publication:967310
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
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