Approximating longest directed paths and cycles

DOI10.1007/978-3-540-27836-8_21MaRDI QIDQ5466464zbMATH OpenOpenAlexFDO

Authors Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99859, https://repository.upenn.edu/cis_papers/205

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding Long Paths, Cycles and Circuits
• On approximating the longest path in a graph
• scientific article; zbMATH DE number 1445365
• On approximating the longest path in a graph
• Finding Paths and Cycles of Superpolylogarithmic Length

Cited in

(43)

• On a simple randomized algorithm for finding a 2-factor in sparse graphs
• Formally verified algorithms for upper-bounding state space diameters
• Towards better models of externalities in sponsored search auctions
• Long directed \((s,t)\)-path: FPT algorithm
• An approximation algorithm for computing longest paths.
• On the longest circuit in an alterable digraph
• On structured output training: hard cases and an efficient alternative
• Note on long paths in Eulerian digraphs
• The maximum binary tree problem
• A note on the approximability of deepest-descent circuit steps
• Approximately counting approximately-shortest paths in directed acyclic graphs
• An approximation algorithm for the longest cycle problem in solid grid graphs
• Path-based mathematical morphology on tensor fields
• Approximating the Longest Cycle Problem in Sparse Graphs
• Integer programming formulations for the elementary shortest path problem
• Evaluation and enumeration problems for regular path queries
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Finding Long Paths, Cycles and Circuits
• scientific article; zbMATH DE number 3948312 (Why is no real title available?)
• scientific article; zbMATH DE number 3974318 (Why is no real title available?)
• On finding the longest antisymmetric path in directed acyclic graphs
• Computing Directed Pathwidth in O(1.89 n ) Time
• Divergence and quasi-isometry classes of random Gromov’s monsters
• Finding a long directed cycle
• On approximating the longest path in a graph
• Finding Paths and Cycles of Superpolylogarithmic Length
• scientific article; zbMATH DE number 6469131 (Why is no real title available?)
• The Maximum Binary Tree Problem.
• scientific article; zbMATH DE number 7746259 (Why is no real title available?)
• Inapproximability of shortest paths on perfect matching polytopes
• The negative cycles polyhedron and hardness of checking some polyhedral properties
• Approximating long cycle above Dirac's guarantee
• On pumping preserving homomorphisms and the complexity of the pumping problem (extended abstract)
• On approximating the longest path in a graph
• Approximating maximum-size properly colored forests
• On the hardness of short and sign-compatible circuit walks
• Inapproximability of shortest paths on perfect matching polytopes
• SAT-based learning of computation tree logic
• Constructing long paths in graph streams
• AI Planning Languages Semantics
• Verified SAT-Based AI Planning
• Upper Bounding Diameters of State Spaces of Factored Transition Systems
• Finding large cycles in Hamiltonian graphs

This page was built for publication: Approximating longest directed paths and cycles

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