Finding a Path of Superlogarithmic Length

DOI10.1137/S0097539702416761MaRDI QIDQ4429693zbMATH OpenOpenAlexWikidataFDO

Authors Andreas Björklund, Thore Husfeldt

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

approximation algorithmsgraph algorithmslongest path

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2086688
• Finding paths and cycles of superpolylogarithmic length
• Finding Paths and Cycles of Superpolylogarithmic Length
• Finding Long Paths, Cycles and Circuits
• scientific article; zbMATH DE number 3974318

Cited in

(22)

• An approximation algorithm for the longest path problem in solid grid graphs
• On the approximability of some degree-constrained subgraph problems
• On a simple randomized algorithm for finding a 2-factor in sparse graphs
• Longest (s, t)-paths in L-shaped grid graphs
• Approximating the maximum clique minor and some subgraph homeomorphism problems
• Formally verified algorithms for upper-bounding state space diameters
• Algorithm for two disjoint long paths in 2-connected graphs
• Approximating the longest paths in grid graphs
• Finding Paths and Cycles of Superpolylogarithmic Length
• Finding paths and cycles of superpolylogarithmic length
• scientific article; zbMATH DE number 2086688 (Why is no real title available?)
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
• A linear-time algorithm for the longest path problem in rectangular grid graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity
• Algorithms for long paths in graphs
• Finding large cycles in Hamiltonian graphs
• An approximation algorithm for the longest cycle problem in solid grid graphs
• A genetic algorithm for the picture maze generation problem
• On computing longest paths in small graph classes
• Approximating long cycle above Dirac's guarantee

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

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