Cyclability in graph classes

DOI10.1016/j.dam.2022.01.021zbMath1485.05156OpenAlexW2991579492MaRDI QIDQ833007

Christophe Crespelle, Petr A. Golovach

Publication date: 28 March 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2022.01.021

zbMATH Keywords

cographsinterval graphscyclabilitycertifying algorithmsbipartite permutation graphs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (1)

Cyclability, connectivity and circumference

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Certifying algorithms
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• A look at cycles containing specified elements of a graph
• Finding Hamiltonian circuits in interval graphs
• Bipartite permutation graphs
• Complement reducible graphs
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Paths in interval graphs and circular arc graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On a class of posets and the corresponding comparability graphs
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• 1-tough cocomparability graphs are hamiltonian
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• HAMILTONian circuits in chordal bipartite graphs
• A framework for the verification of certifying computations
• The Hamiltonian problem on distance-hereditary graphs
• Tough graphs and Hamiltonian circuits.
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Graph Classes: A Survey
• Deferred-query: An efficient approach for some problems on interval graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs
• Parameterized Algorithms
• The Parameterized Complexity of Graph Cyclability

This page was built for publication: Cyclability in graph classes