On approximating the longest path in a graph

DOI10.1007/3-540-57155-8_267zbMath1504.68171OpenAlexW1779055272MaRDI QIDQ5060133

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

Mathematics Subject Classification ID

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

The NPO-completeness of the longest Hamiltonian cycle problem ⋮ On the approximability of some maximum spanning tree problems ⋮ On the approximability of some Maximum Spanning Tree Problems ⋮ A genetic algorithm for the picture maze generation problem ⋮ Partial and perfect path covers of cographs

Cites Work

• On the complexity of approximating the independent set problem
• The Traveling Salesman Problem with Distances One and Two
• Approximating maximum independent sets by excluding subgraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On approximating the longest path in a graph