Finding Long Paths, Cycles and Circuits

DOI10.1007/978-3-540-92182-0_66MaRDI QIDQ3597877zbMATH OpenOpenAlexWikidataFDO

Authors Harold N. Gabow, Shuxin Nie

Publication date 29 January 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92182-0_66

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Finding Paths and Cycles of Superpolylogarithmic Length
• Finding paths and cycles of superpolylogarithmic length
• Automata, Languages and Programming
• Finding a long directed cycle
• On approximating the longest path in a graph

Cited in

(33)

• An approximation algorithm for computing longest paths.
• On the longest circuit in an alterable digraph
• The longest path problem is polynomial on cocomparability graphs
• Note on long paths in Eulerian digraphs
• A genetic algorithm for the picture maze generation problem
• Two edge-disjoint paths with length constraints
• A randomized algorithm for long directed cycle
• An approximation algorithm for the longest cycle problem in solid grid graphs
• Finding large cycles in Hamiltonian graphs
• The longest path problem is polynomial on cocomparability graphs
• Finding two edge-disjoint paths with length constraints
• The Longest Path Problem Is Polynomial on Interval Graphs
• scientific article; zbMATH DE number 3948312 (Why is no real title available?)
• scientific article; zbMATH DE number 3974318 (Why is no real title available?)
• scientific article; zbMATH DE number 4077268 (Why is no real title available?)
• Finding a Path of Superlogarithmic Length
• scientific article; zbMATH DE number 2086688 (Why is no real title available?)
• Finding a long directed cycle
• Going far from degeneracy
• ETH-tight algorithms for long path and cycle on unit disk graphs
• Finding detours is fixed-parameter tractable
• Going far from degeneracy
• Longest (s, t)-paths in L-shaped grid graphs
• Finding Paths and Cycles of Superpolylogarithmic Length
• Automata, Languages and Programming
• scientific article; zbMATH DE number 6469131 (Why is no real title available?)
• scientific article; zbMATH DE number 7746259 (Why is no real title available?)
• The longest path problem has a polynomial solution on interval graphs
• Approximating long cycle above Dirac's guarantee
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• Algorithms for long paths in graphs
• Finding the longest isometric cycle in a graph
• Finding large cycles in Hamiltonian graphs

This page was built for publication: Finding Long Paths, Cycles and Circuits

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