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

DOI10.1007/S00453-023-01107-1MaRDI QIDQ6174822

Jesse Beisegel, Ekkehard Köhler, Martin Strehler, Robert Scheffler

Publication date: 17 August 2023

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian cycleschain graphsHamiltonian pathsthreshold graphsdifference graphsfully dynamic algorithms

Mathematics Subject Classification ID

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

This page was built for publication: Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs