Cyclability in graph classes

DOI10.1016/J.DAM.2022.01.021zbMATH Open1485.05156OpenAlexW2991579492MaRDI QIDQ833007FDOQ833007

Authors: 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

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Graph Classes: A Survey
• Complement reducible graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Title not available (Why is that?)
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Parameterized algorithms
• Bipartite permutation graphs
• HAMILTONian circuits in chordal bipartite graphs
• A look at cycles containing specified elements of a graph
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• The Hamiltonian problem on distance-hereditary graphs
• Finding Hamiltonian circuits in interval graphs
• Tough graphs and Hamiltonian circuits.
• On a class of posets and the corresponding comparability graphs
• Certifying algorithms
• Title not available (Why is that?)
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• Paths in interval graphs and circular arc graphs
• A framework for the verification of certifying computations
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Deferred-query: An efficient approach for some problems on interval graphs
• 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
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Title not available (Why is that?)
• 1-tough cocomparability graphs are hamiltonian
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs

Cited In (3)

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

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)