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

DOI10.1007/S00453-023-01107-1MaRDI QIDQ6174822zbMATH OpenFDO

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

Publication date 17 August 2023

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-023-01107-1

zbMATH Keywords

chain graphsdifference graphsfully dynamic algorithmsHamiltonian cyclesHamiltonian pathsthreshold graphs

Mathematics Subject Classification ID

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

Cites work

• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A fully dynamic approximation scheme for shortest paths in planar graphs
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Algorithmic Aspects of Vertex Elimination on Graphs
• Cyclic scheduling of offweekends
• Difference graphs
• Edge elimination and weighted graph classes
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
• Fully dynamic algorithms for chordal graphs and split graphs
• Fully dynamic biconnectivity in graphs
• Fully dynamic recognition of proper circular-arc graphs
• Fully dynamic shortest paths in digraphs with arbitrary arc weights
• Fully dynamically maintaining minimal integral separator for threshold and difference graphs
• Graph Classes: A Survey
• Hamiltonian threshold graphs
• scientific article; zbMATH DE number 4043213 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Lower bounds for fully dynamic connectivity problems in graphs
• Minimal Threshold Separators and Memory Requirements for Synchronization
• Multidimensional scaling and threshold graphs
• Near-optimal fully-dynamic graph connectivity
• New deterministic approximation algorithms for fully dynamic matching
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions
• The Complexity of the Partial Order Dimension Problem
• Threshold Dimension of Graphs
• Threshold graphs and related topics

Cited in

(3)

• On certificates and lookahead in dynamic graph problems
• An O(nm)-Time Certifying Algorithm for Recognizing HHD-Free Graphs
• Computing Hamiltonian paths with partial order restrictions

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

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