Dynamically maintaining split graphs
type: Item
instance of: scholarly article
title: Dynamically maintaining split graphs
zbMATH Open document ID: 1179.05106
author: Pinar Heggernes
author: F. Mancini
published in: Discrete Applied Mathematics
publication date: 2009-06-24T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C76
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5569438
zbMATH Keywords: split graphs
zbMATH Keywords: dynamic algorithms
zbMATH Keywords: on-line algorithms
zbMATH Keywords: minimal split completions
MaRDI profile type: Publication
full work available at URL: j.dam.2008.06.028
OpenAlex ID: W2032400288
cites work: Q3138872
cites work: Split-Perfect Graphs: Characterizations and Algorithmic Use
cites work: Graph Classes: A Survey
cites work: Graphs with no induced \(C_ 4\) and \(2K_ 2\)
cites work: A vertex incremental approach for maintaining chordality
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
cites work: A Linear Recognition Algorithm for Cographs
cites work: Graph-Theoretic Concepts in Computer Science
cites work: A new approach to dynamic all pairs shortest paths
cites work: Q4193514
cites work: Algorithmic graph theory and perfect graphs
cites work: The splittance of a graph
cites work: Minimal Split Completions of Graphs
cites work: Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions
cites work: Algorithms – ESA 2005
cites work: Interval Completion Is Fixed Parameter Tractable
cites work: Q4252412
cites work: Fully dynamic algorithms for chordal graphs and split graphs
cites work: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
cites work: An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
cites work: Characterizing and Computing Minimal Cograph Completions
cites work: Linear recognition of pseudo-split graphs
cites work: Split-neighbourhood graphs and the strong perfect graph conjecture
cites work: Chordal Deletion Is Fixed-Parameter Tractable
cites work: Obtaining a Planar Graph by Vertex Deletion
cites work: Q4526775
cites work: Split graphs
cites work: Complexity classification of some edge modification problems
cites work: A Fully dynamic algorithm for recognizing and representing proper interval graphs
DOI: 10.1016/J.DAM.2008.06.028
description: scientific article; zbMATH DE number 5569438