Recommendations
- On approximating the longest path in a graph
- Approximating the longest paths in grid graphs
- Approximating Shortest Paths in Graphs
- Automata, Languages and Programming
- An approximation algorithm for computing longest paths.
- scientific article; zbMATH DE number 1445365
- An approximation algorithm for finding long paths in Hamiltonian graphs
- Algorithms for long paths in graphs
- On computing longest paths in small graph classes
- Bounding the distance among longest paths in a connected graph
Cites work
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256635 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 742978 (Why is no real title available?)
- Approximate graph coloring by semidefinite programming
- Bin packing can be solved within 1+epsilon in linear time
- Edmonds polytopes and weakly hamiltonian graphs
- Finding hidden hamiltonian cycles
- On the complexity of approximating the independent set problem
- On the hardness of approximating minimization problems
- The NP-completeness column: An ongoing guide
- The Traveling Salesman Problem with Distances One and Two
- Tough graphs and Hamiltonian circuits.
Cited in
(79)- On the Power of Planned Infections in Networks
- Minimal functional routes in directed graphs with dependent edges
- A polynomial-time approximation scheme for thief orienteering on directed acyclic graphs
- Algorithms for the thief orienteering problem on directed acyclic graphs
- Optimizing concurrency under Scheduling by Edge Reversal
- The longest path problem in odd-sized \(O\)-shaped grid graphs
- On Approximating the d-Girth of a Graph
- MIP formulations for induced graph optimization problems: a tutorial
- On approximating the \(d\)-girth of a graph
- QUBO formulations of the longest path problem
- Social distancing network creation
- Improved approximation algorithms for the \(k\)-path partition problem
- A streaming algorithm for the undirected longest path problem
- Approximating long cycle above Dirac's guarantee
- APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD
- An approximation algorithm for the longest path problem in solid grid graphs
- The Longest Path Problem Is Polynomial on Interval Graphs
- On the approximability of some degree-constrained subgraph problems
- On a simple randomized algorithm for finding a 2-factor in sparse graphs
- An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
- Finding Long Paths, Cycles and Circuits
- Longest (s, t)-paths in L-shaped grid graphs
- Approximating the maximum clique minor and some subgraph homeomorphism problems
- Cycles and new bounds for the chromatic number
- Spanning spiders and light-splitting switches
- Well-mixing vertices and almost expanders
- The complexity of bottleneck labeled graph problems
- The maximum binary tree problem
- Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
- Automata, Languages and Programming
- New results for the longest haplotype reconstruction problem
- The maximum resource bin packing problem
- Approximating the longest paths in grid graphs
- On finding spanning trees with few leaves
- Linear structure of bipartite permutation graphs and the longest path problem
- Computing and counting longest paths on circular-arc graphs in polynomial time
- Networks of polynomial pieces with application to the analysis of point clouds and images
- The Maximum Binary Tree Problem.
- Maintaining longest paths incrementally
- Degree-Constrained Subgraph Problems: Hardness and Approximation Results
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
- On the length of simplex paths: The assignment case
- The distribution of first hitting times of randomwalks on Erdős-Rényi networks
- Drawing graphs in two layers
- The Complexity of Bottleneck Labeled Graph Problems
- On exact solution approaches for the longest induced path problem
- The distribution of first hitting times of non-backtracking random walks on Erdos-Rényi networks
- A linear-time algorithm for the longest path problem in rectangular grid graphs
- The density maximization problem in graphs
- The longest path problem is polynomial on cocomparability graphs
- Finding monotone paths in edge-ordered graphs
- Dendrograms, minimum spanning trees and feature selection
- On approximating the longest path in a graph
- Approximate solution of NP optimization problems
- Computing and counting longest paths on circular-arc graphs in polynomial time
- Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
- Approximation algorithms and hardness results for labeled connectivity problems
- Algorithms for long paths in graphs
- An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
- The lazy bureaucrat scheduling problem
- Integer programming formulations for the elementary shortest path problem
- On lazy bureaucrat scheduling with common deadlines
- scientific article; zbMATH DE number 1445365 (Why is no real title available?)
- An approximation algorithm for computing longest paths.
- On the approximation of shortest common supersequences and longest common subsequences
- An approximation algorithm for finding long paths in Hamiltonian graphs
- Scheduling for single agile satellite, redundant targets problem using complex networks theory
- Exact methods for solving the elementary shortest and longest path problems
- Finding large cycles in Hamiltonian graphs
- An approximation algorithm for the longest cycle problem in solid grid graphs
- Path-based mathematical morphology on tensor fields
- Bounding the distance among longest paths in a connected graph
- On computing longest paths in small graph classes
- On approximating maximum covering cycles in undirected graphs
- The longest path problem has a polynomial solution on interval graphs
- Tropical paths in vertex-colored graphs
- On finding the longest antisymmetric path in directed acyclic graphs
- Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
This page was built for publication: On approximating the longest path in a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679451)
