Finding large cycles in Hamiltonian graphs

DOI10.1016/j.dam.2009.12.006zbMath1225.05147OpenAlexW2093577684MaRDI QIDQ972323

Rajeev Motwani, Tomás Feder

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

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

Related Items (3)

Find subtrees of specified weight and cycles of specified length in linear time ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs

Cites Work

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

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