Finding large cycles in Hamiltonian graphs

DOI10.1016/J.DAM.2009.12.006zbMATH Open1225.05147OpenAlexW2093577684MaRDI QIDQ972323FDOQ972323

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

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

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)

Cites Work

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

Cited In (9)

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

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)