Cyclability in graph classes

DOI10.1016/J.DAM.2022.01.021MaRDI QIDQ833007zbMATH OpenOpenAlexFDO

Authors Christophe Crespelle, Petr A. Golovach

Publication date 28 March 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

interval graphscographscyclabilitycertifying algorithmsbipartite permutation graphs

Mathematics Subject Classification ID

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

Recommendations

• Cyclable cube of a graph
• Cyclability in bipartite graphs
• On the cyclability of graphs

Cites work

• scientific article; zbMATH DE number 3919840 (Why is no real title available?)
• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7053391 (Why is no real title available?)
• 1-tough cocomparability graphs are hamiltonian
• A framework for the verification of certifying computations
• A look at cycles containing specified elements of a graph
• Algorithmic graph theory and perfect graphs
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Bipartite permutation graphs
• Certifying algorithms
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• Complement reducible graphs
• Deferred-query: An efficient approach for some problems on interval graphs
• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Graph Classes: A Survey
• Graph minors. XIII: The disjoint paths problem
• HAMILTONian circuits in chordal bipartite graphs
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• On a class of posets and the corresponding comparability graphs
• Parameterized algorithms
• Paths in interval graphs and circular arc graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Hamiltonian problem on distance-hereditary graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Tough graphs and Hamiltonian circuits.

Cited in

(3)

• Cyclic separability in graphs
• Cyclability, connectivity and circumference
• Class I graphs of nonnegative characteristic without special cycles

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Cyclability in graph classes

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