Fully dynamically maintaining minimal integral separator for threshold and difference graphs

DOI10.1007/978-3-319-30139-6_25zbMATH Open1475.68232OpenAlexW2460038360MaRDI QIDQ2803835FDOQ2803835

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

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

zbMATH Keywords

graph operationschain graphsthreshold graphsdifference graphsfully dynamic graphsthreshold signed graphs

Mathematics Subject Classification ID

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

Cites Work

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

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)