Dynamically maintaining split graphs
From MaRDI portal
Publication:1026107
DOI10.1016/j.dam.2008.06.028zbMath1179.05106OpenAlexW2032400288MaRDI QIDQ1026107
Federico Mancini, Pinar Heggernes
Publication date: 24 June 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.06.028
Graph theory (including graph drawing) in computer science (68R10) 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 (6)
On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ Characterizing and computing minimal cograph completions ⋮ Fully dynamic recognition of proper circular-arc graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A vertex incremental approach for maintaining chordality
- The splittance of a graph
- Linear recognition of pseudo-split graphs
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Graphs with no induced \(C_ 4\) and \(2K_ 2\)
- Split graphs
- Algorithmic graph theory and perfect graphs
- Split-neighbourhood graphs and the strong perfect graph conjecture
- An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- Characterizing and Computing Minimal Cograph Completions
- Obtaining a Planar Graph by Vertex Deletion
- Chordal Deletion Is Fixed-Parameter Tractable
- Minimal Split Completions of Graphs
- A new approach to dynamic all pairs shortest paths
- Interval Completion Is Fixed Parameter Tractable
- A Linear Recognition Algorithm for Cographs
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Graph Classes: A Survey
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Split-Perfect Graphs: Characterizations and Algorithmic Use
- Fully dynamic algorithms for chordal graphs and split graphs
- Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions
- Algorithms – ESA 2005
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Complexity classification of some edge modification problems
This page was built for publication: Dynamically maintaining split graphs
