On approximating the longest path in a graph

DOI10.1007/3-540-57155-8_267MaRDI QIDQ5060133zbMATH OpenOpenAlexFDO

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

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

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 finding long paths in Hamiltonian graphs
• scientific article; zbMATH DE number 1445365
• An approximation algorithm for the longest path problem in solid grid graphs
• An approximation algorithm for computing longest paths.
• Exact and approximate algorithms for the longest induced path problem
• On computing longest paths in small graph classes

Cites work

• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3974318 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (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?)
• Approximating maximum independent sets by excluding subgraphs
• On the complexity of approximating the independent set problem
• The Traveling Salesman Problem with Distances One and Two

Cited in

(16)

• On the approximability of some maximum spanning tree problems
• Longest-edge \(n\)-section algorithms: properties and open problems
• On approximating the longest path in a graph
• An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
• Bounding the distance among longest paths in a connected graph
• An approximation algorithm for computing longest paths.
• 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
• scientific article; zbMATH DE number 1445365 (Why is no real title available?)
• On finding the longest antisymmetric path in directed acyclic graphs
• Automata, Languages and Programming
• An approximation algorithm for finding long paths in Hamiltonian graphs
• 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 Q5060133)