Finding large cycles in Hamiltonian graphs

DOI10.1016/j.dam.2009.12.006zbMath1225.05147MaRDI 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 cycle; planar graph; 3-connected graph; 3-cyclable graph; long cycle in graphs

Mathematics Subject Classification ID

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

05C40: Connectivity

05C45: Eulerian and Hamiltonian graphs

Related Items

Find subtrees of specified weight and cycles of specified length in linear time, Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs, The longest path problem is polynomial on cocomparability 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