On approximating the longest path in a graph
Publication:5060133
DOI10.1007/3-540-57155-8_267zbMATH Open1504.68171OpenAlexW1779055272MaRDI QIDQ5060133FDOQ5060133
Rajeev Motwani, G. D. S. Ramkumar, David R. Karger
Publication date: 18 January 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-57155-8_267
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
- The Traveling Salesman Problem with Distances One and Two
- On the complexity of approximating the independent set problem
- Approximating maximum independent sets by excluding subgraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (13)
- On the approximability of some maximum spanning tree problems
- Longest-edge \(n\)-section algorithms: properties and open problems
- An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
- On approximating the longest path in a graph
- Bounding the distance among longest paths in a connected graph
- Partial and perfect path covers of cographs
- On the approximability of some Maximum Spanning Tree Problems
- The NPO-completeness of the longest Hamiltonian cycle problem
- An improved algorithm for the longest induced path problem on \(k\)-chordal graphs
- A genetic algorithm for the picture maze generation problem
- Title not available (Why is that?)
- On finding the longest antisymmetric path in directed acyclic graphs
- An approximation algorithm for finding long paths in Hamiltonian graphs
Recommendations
- Title not available (Why is that?) 👍 👎
- ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES 👍 👎
- Approximating Shortest Paths in Graphs 👍 👎
- Automata, Languages and Programming 👍 👎
- On approximating the longest path in a graph 👍 👎
- Approximating the longest paths in grid graphs 👍 👎
- An approximation algorithm for computing longest paths. 👍 👎
- An approximation algorithm for finding long paths in Hamiltonian graphs 👍 👎
- An approximation algorithm for the longest path problem in solid grid graphs 👍 👎
- Exact and approximate algorithms for the longest induced path problem 👍 👎
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 Q5060133)
