Finding large cycles in Hamiltonian graphs

DOI10.1016/J.DAM.2009.12.006MaRDI QIDQ972323zbMATH OpenOpenAlexFDO

Authors Tomás Feder, Rajeev Motwani

Publication date 25 May 2010

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

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

zbMATH Keywords

Hamiltonian cycleplanar graph3-connected graph3-cyclable graphlong cycle in graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Connectivity (05C40)

Recommendations

• Finding large cycles in Hamiltonian graphs
• Finding long paths and cycles in sparse Hamiltonian graphs
• Circumference of Graphs with Bounded Degree
• Finding Long Paths, Cycles and Circuits
• Approximating Longest Cycles in Graphs with Bounded Degrees

Cites work

• scientific article; zbMATH DE number 426167 (Why is no real title available?)
• scientific article; zbMATH DE number 742978 (Why is no real title available?)
• Approximating Longest Cycles in Graphs with Bounded Degrees
• Approximating the Longest Cycle Problem in Sparse Graphs
• Automata, Languages and Programming
• Circumference of Graphs with Bounded Degree
• Dividing a Graph into Triconnected Components
• Finding a Path of Superlogarithmic Length
• Finding paths and cycles of superpolylogarithmic length
• Graph minors. XIII: The disjoint paths problem
• Long cycles in 3-connected graphs
• Long cycles in graphs on a fixed surface
• Longest cycles in 3-connected cubic graphs
• On 2-connected spanning subgraphs with low maximum degree
• On approximating the longest path in a graph
• On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
• The subgraph homeomorphism problem

Cited in

(9)

• Finding Hamilton cycles in robustly expanding digraphs
• Long cycles in graphs on a fixed surface
• Find subtrees of specified weight and cycles of specified length in linear time
• The longest path problem is polynomial on cocomparability graphs
• Finding long paths and cycles in sparse Hamiltonian graphs
• Locating any two vertices on Hamiltonian cycles in large graphs
• Finding large cycles in Hamiltonian graphs
• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Approximating long cycle above Dirac's guarantee

This page was built for publication: Finding large cycles in Hamiltonian graphs

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