Dynamically maintaining split graphs

DOI10.1016/J.DAM.2008.06.028MaRDI QIDQ1026107zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, F. Mancini

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

zbMATH Keywords

on-line algorithmssplit graphsdynamic algorithmsminimal split completions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• A completely dynamic algorithm for split graphs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Fully dynamic algorithms for chordal graphs and split graphs
• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• Dynamic Distance Hereditary Graphs Using Split Decomposition

Cites work

• scientific article; zbMATH DE number 432746 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 1305520 (Why is no real title available?)
• scientific article; zbMATH DE number 1557063 (Why is no real title available?)
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A Linear Recognition Algorithm for Cographs
• A new approach to dynamic all pairs shortest paths
• A vertex incremental approach for maintaining chordality
• Algorithmic graph theory and perfect graphs
• Algorithms – ESA 2005
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
• Characterizing and Computing Minimal Cograph Completions
• Chordal Deletion Is Fixed-Parameter Tractable
• Complexity classification of some edge modification problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fully dynamic algorithms for chordal graphs and split graphs
• Graph Classes: A Survey
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• Interval Completion Is Fixed Parameter Tractable
• Linear recognition of pseudo-split graphs
• Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions
• Minimal Split Completions of Graphs
• Obtaining a Planar Graph by Vertex Deletion
• Split graphs
• Split-Perfect Graphs: Characterizations and Algorithmic Use
• Split-neighbourhood graphs and the strong perfect graph conjecture
• The splittance of a graph
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs

Cited in

(9)

• On the effectiveness of the incremental approach to minimal chordal edge modification
• Characterizing and computing minimal cograph completions
• Fully dynamic recognition of proper circular-arc graphs
• Fully dynamically maintaining minimal integral separator for threshold and difference graphs
• A fully dynamic algorithm for the recognition of P₄-sparse graphs
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• A completely dynamic algorithm for split graphs
• scientific article; zbMATH DE number 1617249 (Why is no real title available?)
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs

This page was built for publication: Dynamically maintaining split graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1026107)