Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs

DOI10.1007/978-3-319-30139-6_25zbMath1475.68232OpenAlexW2460038360MaRDI QIDQ2803835

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 graphsgraph operationsthreshold graphsdifference graphsfully dynamic graphsthreshold signed graphs

Mathematics Subject Classification ID

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

Related Items (1)

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

Cites Work

• Unnamed Item
• 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.
• Threshold graphs and related topics
• The Complexity of the Partial Order Dimension Problem
• Threshold characterization of graphs with dilworth number two
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives

This page was built for publication: Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs