Finding a path of superlogarithmic length
Author
Summary, in English
We consider the problem of finding a long, simple path in an undirected graph. We present a polynomial-time algorithm that finds a path of length Omega((log L/log log L)(2)), where L denotes the length of the longest simple path in the graph. This establishes the performance ratio O(n( log log n/log n)(2)) for the longest path problem, where n denotes the number of vertices in the graph.
Department/s
- Department of Computer Science
- Computer Science
- Parallel Systems
Publishing year
2003
Language
English
Pages
1395-1402
Publication/Series
SIAM Journal on Computing
Volume
32
Issue
6
Document type
Journal article
Publisher
Society for Industrial and Applied Mathematics
Topic
- Computer Science
Keywords
- longest path
- approximation algorithms
- graph algorithms
Status
Published
ISBN/ISSN/Other
- ISSN: 0097-5397