On approximating the longest path in a graph

DOI10.1007/BF02523689MaRDI QIDQ679451zbMATH OpenDBLPWikidataFDO

Authors G. D. S. Ramkumar, David R. Karger, Rajeev Motwani

Publication date 12 November 1997

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02523689

zbMATH Keywords

greedy algorithmundirected graphs

Mathematics Subject Classification ID

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)

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

(81)

• 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
• Linear structure of bipartite permutation graphs and the longest path problem
• Tropical paths in vertex-colored graphs
• The maximum binary tree problem
• APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD
• Networks of polynomial pieces with application to the analysis of point clouds and images
• On approximating the \(d\)-girth of a graph
• Finding large cycles in Hamiltonian graphs
• 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
• 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
• An approximation algorithm for computing longest paths.
• New results for the longest haplotype reconstruction problem
• On the Power of Planned Infections in Networks
• The lazy bureaucrat scheduling problem
• Finding monotone paths in edge-ordered graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• On Approximating the d-Girth of a Graph
• Approximating long cycle above Dirac's guarantee
• The distribution of first hitting times of randomwalks on Erdős-Rényi networks
• On the length of simplex paths: The assignment case
• The distribution of first hitting times of non-backtracking random walks on Erdos-Rényi networks
• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Cycles and new bounds for the chromatic number
• Longest (s, t)-paths in L-shaped grid graphs
• Approximating the maximum clique minor and some subgraph homeomorphism problems
• On computing longest paths in small graph classes
• Approximate solution of NP optimization problems
• On approximating the longest path in a graph
• MIP formulations for induced graph optimization problems: a tutorial
• An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
• On lazy bureaucrat scheduling with common deadlines
• A polynomial-time approximation scheme for thief orienteering on directed acyclic graphs
• Integer programming formulations for the elementary shortest path problem
• QUBO formulations of the longest path problem
• A streaming algorithm for the undirected longest path problem
• Complexity results and algorithms for representing paths in digraphs
• scientific article; zbMATH DE number 1445365 (Why is no real title available?)
• On exact solution approaches for the longest induced path problem
• On finding the longest antisymmetric path in directed acyclic graphs
• The longest path problem is polynomial on cocomparability graphs
• The Complexity of Bottleneck Labeled Graph Problems
• Improved approximation algorithms for the \(k\)-path partition problem
• The longest path problem has a polynomial solution on interval graphs
• On a simple randomized algorithm for finding a 2-factor in sparse graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• Automata, Languages and Programming
• Optimizing concurrency under Scheduling by Edge Reversal
• Approximating the longest path length of a stochastic DAG by a normal distribution in linear time
• The longest path problem in odd-sized O-shaped grid graphs
• The Longest Path Problem Is Polynomial on Interval Graphs
• AxSAT -- bringing axioms to SAT planning
• Algorithms for long paths in graphs
• Well-mixing vertices and almost expanders
• Maintaining longest paths incrementally
• Algorithms for the thief orienteering problem on directed acyclic graphs
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Finding Long Paths, Cycles and Circuits
• Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• On approximating maximum covering cycles in undirected graphs
• An approximation algorithm for finding long paths in Hamiltonian graphs
• The Maximum Binary Tree Problem.
• Social distancing network creation
• Scheduling for single agile satellite, redundant targets problem using complex networks theory
• Exact methods for solving the elementary shortest and longest path problems
• Minimal functional routes in directed graphs with dependent edges
• Path-based mathematical morphology on tensor fields
• Spanning spiders and light-splitting switches
• On the approximation of shortest common supersequences and longest common subsequences
• On finding spanning trees with few leaves
• Approximation algorithms and hardness results for labeled connectivity problems
• The density maximization problem in graphs
• The maximum resource bin packing problem
• Dendrograms, minimum spanning trees and feature selection
• On the approximability of some degree-constrained subgraph problems
• An approximation algorithm for the longest path problem in solid grid 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)