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

Algorithms in computer science (68Wxx) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Graph theory (05Cxx)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
Cyclic scheduling of offweekends
Hamiltonian threshold graphs
Multidimensional scaling and threshold graphs
A fully dynamic approximation scheme for shortest paths in planar graphs
Lower bounds for fully dynamic connectivity problems in graphs
A fully dynamic algorithm for modular decomposition and recognition of cographs.
Fully dynamic biconnectivity in graphs
Threshold graphs and related topics
Edge elimination and weighted graph classes
Fully dynamic recognition of proper circular-arc graphs
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs
Near-optimal fully-dynamic graph connectivity
Threshold Dimension of Graphs
Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions
The Complexity of the Partial Order Dimension Problem
Minimal Threshold Separators and Memory Requirements for Synchronization
A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
Algorithmic Aspects of Vertex Elimination on Graphs
Graph Classes: A Survey
Fully dynamic shortest paths in digraphs with arbitrary arc weights
Fully dynamic algorithms for chordal graphs and split graphs
New deterministic approximation algorithms for fully dynamic matching
Difference graphs
Fully dynamic algorithm for recognition and modular decomposition of permutation graphs