Finding a Path of Superlogarithmic Length

DOI10.1137/S0097539702416761zbMath1041.68066OpenAlexW2046496468WikidataQ56639262 ScholiaQ56639262MaRDI QIDQ4429693

Thore Husfeldt, Andreas Björklund

Publication date: 28 September 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539702416761

zbMATH Keywords

graph algorithmsapproximation algorithmslongest path

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (18)

An approximation algorithm for the longest cycle problem in solid grid graphs ⋮ Formally verified algorithms for upper-bounding state space diameters ⋮ Algorithms for long paths in graphs ⋮ On the approximability of some degree-constrained subgraph problems ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ Not being (super)thin or solid is hard: A study of grid Hamiltonicity ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ Finding large cycles in Hamiltonian graphs ⋮ Algorithm for two disjoint long paths in 2-connected graphs ⋮ Approximating the longest paths in grid graphs ⋮ Degree-Constrained Subgraph Problems: Hardness and Approximation Results ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ A genetic algorithm for the picture maze generation problem ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs ⋮ An approximation algorithm for the longest path problem in solid grid graphs ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ A linear-time algorithm for the longest path problem in rectangular grid graphs ⋮ On a simple randomized algorithm for finding a 2-factor in sparse graphs

This page was built for publication: Finding a Path of Superlogarithmic Length