On approximating the longest path in a graph

DOI10.1007/BF02523689zbMATH Open0876.68083DBLPjournals/algorithmica/KargerMR97WikidataQ56639263 ScholiaQ56639263MaRDI QIDQ679451FDOQ679451

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

Publication date: 12 November 1997

Published in: Algorithmica (Search for Journal in Brave)

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

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)

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 (78)

• 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
• On computing longest paths in small graph classes
• 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
• 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
• Finding Long Paths, Cycles and Circuits
• 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

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)