Fully dynamically maintaining minimal integral separator for threshold and difference graphs

DOI10.1007/978-3-319-30139-6_25MaRDI QIDQ2803835zbMATH OpenOpenAlexFDO

Authors Angelo Monti, Rossella Petreschi, Tiziana Calamoneri

Publication date 3 May 2016

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/11573/955323

zbMATH Keywords

chain graphsdifference graphsfully dynamic graphsgraph operationsthreshold graphsthreshold signed graphs

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On dynamic threshold graphs and related classes
• Dynamically maintaining split graphs
• A completely dynamic algorithm for split graphs
• Separator based sparsification. I: Planarity testing and minimum spanning trees
• Maintaining minimum spanning trees in dynamic graphs

Cites work

• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Ferrers digraphs and threshold graphs
• scientific article; zbMATH DE number 3561379 (Why is no real title available?)
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• The Complexity of the Partial Order Dimension Problem
• Threshold characterization of graphs with dilworth number two
• Threshold graphs and related topics

Cited in

(1)

• Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs

This page was built for publication: Fully dynamically maintaining minimal integral separator for threshold and difference graphs

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