On approximating the longest path in a graph
From MaRDI portal
Publication:679451
DOI10.1007/BF02523689zbMath0876.68083DBLPjournals/algorithmica/KargerMR97WikidataQ56639263 ScholiaQ56639263MaRDI QIDQ679451
G. D. S. Ramkumar, David R. Karger
Publication date: 12 November 1997
Published in: Algorithmica (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (60)
An approximation algorithm for the longest cycle problem in solid grid graphs ⋮ Spanning spiders and light-splitting switches ⋮ Drawing graphs in two layers ⋮ Well-mixing vertices and almost expanders ⋮ APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD ⋮ Linear structure of bipartite permutation graphs and the longest path problem ⋮ On finding spanning trees with few leaves ⋮ The Longest Path Problem Is Polynomial on Interval Graphs ⋮ Integer programming formulations for the elementary shortest path problem ⋮ Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths ⋮ Networks of polynomial pieces with application to the analysis of point clouds and images ⋮ QUBO formulations of the longest path problem ⋮ Finding monotone paths in edge-ordered graphs ⋮ The density maximization problem in graphs ⋮ Algorithms for long paths in graphs ⋮ On approximating maximum covering cycles in undirected graphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Optimizing concurrency under Scheduling by Edge Reversal ⋮ The lazy bureaucrat scheduling problem ⋮ Social distancing network creation ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ The Complexity of Bottleneck Labeled Graph Problems ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ On lazy bureaucrat scheduling with common deadlines ⋮ Dendrograms, minimum spanning trees and feature selection ⋮ New results for the longest haplotype reconstruction problem ⋮ A polynomial-time approximation scheme for thief orienteering on directed acyclic graphs ⋮ The longest path problem has a polynomial solution on interval graphs ⋮ On the approximability of some degree-constrained subgraph problems ⋮ The distribution of first hitting times of randomwalks on Erdős–Rényi networks ⋮ On approximating the \(d\)-girth of a graph ⋮ Longest (s, t)-paths in L-shaped grid graphs ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ On the approximation of shortest common supersequences and longest common subsequences ⋮ The Maximum Binary Tree Problem. ⋮ Approximate solution of NP optimization problems ⋮ Scheduling for single agile satellite, redundant targets problem using complex networks theory ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ Algorithm engineering for color-coding with applications to signaling pathway detection ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs ⋮ Minimal functional routes in directed graphs with dependent edges ⋮ Finding large cycles in Hamiltonian graphs ⋮ Approximating the longest paths in grid graphs ⋮ Degree-Constrained Subgraph Problems: Hardness and Approximation Results ⋮ Tropical paths in vertex-colored graphs ⋮ The maximum resource bin packing problem ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ The complexity of bottleneck labeled graph problems ⋮ The maximum binary tree problem ⋮ Path-Based Mathematical Morphology on Tensor Fields ⋮ On Approximating the d-Girth of a Graph ⋮ Linear-time algorithms for finding Hamiltonian and longest \((s,t)\)-paths in \(C\)-shaped grid graphs ⋮ An approximation algorithm for the longest path problem in solid grid graphs ⋮ An approximation algorithm for computing longest paths. ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ A linear-time algorithm for the longest path problem in rectangular grid graphs ⋮ On the Power of Planned Infections in Networks ⋮ On a simple randomized algorithm for finding a 2-factor in sparse graphs ⋮ Cycles and new bounds for the chromatic number ⋮ The distribution of first hitting times of non-backtracking random walks on Erdős–Rényi networks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bin packing can be solved within 1+epsilon in linear time
- On the complexity of approximating the independent set problem
- Tough graphs and Hamiltonian circuits.
- Approximate graph coloring by semidefinite programming
- Finding hidden hamiltonian cycles
- The Traveling Salesman Problem with Distances One and Two
- On the hardness of approximating minimization problems
- Edmonds polytopes and weakly hamiltonian graphs
- The NP-completeness column: An ongoing guide
This page was built for publication: On approximating the longest path in a graph
