On approximating the longest path in a graph

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

Cites Work

Title not available (Why is that?)
Approximate graph coloring by semidefinite programming
Bin packing can be solved within 1+epsilon in linear time
The Traveling Salesman Problem with Distances One and Two
Title not available (Why is that?)
Title not available (Why is that?)
On the hardness of approximating minimization problems
On the complexity of approximating the independent set problem
Title not available (Why is that?)
Tough graphs and Hamiltonian circuits.
Edmonds polytopes and weakly hamiltonian graphs
Title not available (Why is that?)
Finding hidden hamiltonian cycles
The NP-completeness column: An ongoing guide

Cited In (77)

Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
An approximation algorithm for the longest cycle problem in solid grid graphs
Tropical paths in vertex-colored graphs
Linear structure of bipartite permutation graphs and the longest path problem
APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD
The maximum binary tree problem
Networks of polynomial pieces with application to the analysis of point clouds and images
Path-Based Mathematical Morphology on Tensor Fields
The complexity of bottleneck labeled graph problems
An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
Finding large cycles in Hamiltonian graphs
Approximating the longest paths in grid graphs
A linear-time algorithm for the longest path problem in rectangular grid graphs
Bounding the distance among longest paths in a connected graph
Drawing graphs in two layers
The distribution of first hitting times of randomwalks on Erdős–Rényi networks
An approximation algorithm for computing longest paths.
New results for the longest haplotype reconstruction problem
The lazy bureaucrat scheduling problem
Computing and counting longest paths on circular-arc graphs in polynomial time
Finding monotone paths in edge-ordered graphs
On the length of simplex paths: The assignment case
Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
Longest (s, t)-paths in L-shaped grid graphs
Cycles and new bounds for the chromatic number
Approximating the maximum clique minor and some subgraph homeomorphism problems
On approximating the longest path in a graph
Approximate solution of NP optimization problems
An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
On lazy bureaucrat scheduling with common deadlines
Integer programming formulations for the elementary shortest path problem
Title not available (Why is that?)
On exact solution approaches for the longest induced path problem
On finding the longest antisymmetric path in directed acyclic graphs
The Complexity of Bottleneck Labeled Graph Problems
The longest path problem is polynomial on cocomparability graphs
The longest path problem has a polynomial solution on interval graphs
On a simple randomized algorithm for finding a 2-factor in sparse graphs
Automata, Languages and Programming
ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
Computing and counting longest paths on circular-arc graphs in polynomial time
The Longest Path Problem Is Polynomial on Interval Graphs
Well-mixing vertices and almost expanders
Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
Algorithms for long paths in graphs
Maintaining longest paths incrementally
Degree-Constrained Subgraph Problems: Hardness and Approximation Results
Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
Algorithm engineering for color-coding with applications to signaling pathway detection
An approximation algorithm for finding long paths in Hamiltonian graphs
On approximating maximum covering cycles in undirected graphs
The Maximum Binary Tree Problem.
Scheduling for single agile satellite, redundant targets problem using complex networks theory
Exact methods for solving the elementary shortest and longest path problems
On the approximation of shortest common supersequences and longest common subsequences
Spanning spiders and light-splitting switches
On finding spanning trees with few leaves
Dendrograms, minimum spanning trees and feature selection
Approximation algorithms and hardness results for labeled connectivity problems
The maximum resource bin packing problem
The density maximization problem in graphs
An approximation algorithm for the longest path problem in solid grid graphs
On the approximability of some degree-constrained subgraph problems
The distribution of first hitting times of non-backtracking random walks on Erdős–Rényi networks
On approximating the \(d\)-girth of a graph
On the Power of Planned Infections in Networks
Approximating long cycle above Dirac's guarantee
On Approximating the d-Girth of a Graph
MIP formulations for induced graph optimization problems: a tutorial
A polynomial-time approximation scheme for thief orienteering on directed acyclic graphs
QUBO formulations of the longest path problem
Improved approximation algorithms for the \(k\)-path partition problem
Optimizing concurrency under Scheduling by Edge Reversal
The longest path problem in odd-sized \(O\)-shaped grid graphs
Algorithms for the thief orienteering problem on directed acyclic graphs
Social distancing network creation
Minimal functional routes in directed graphs with dependent edges

   Recommendations

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)