Finding a path of superlogarithmic length
(2003) In SIAM Journal on Computing 32(6). p.1395-1402- Abstract
- 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.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/294049
- author
- Björklund, Andreas LU and Husfeldt, Thore LU
- organization
- publishing date
- 2003
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- longest path, approximation algorithms, graph algorithms
- in
- SIAM Journal on Computing
- volume
- 32
- issue
- 6
- pages
- 1395 - 1402
- publisher
- Society for Industrial and Applied Mathematics
- external identifiers
-
- wos:000186766600001
- scopus:0942288266
- ISSN
- 0097-5397
- DOI
- 10.1137/S0097539702416761
- language
- English
- LU publication?
- yes
- id
- 06da6959-ea37-4b66-b805-0b5f2fbba17c (old id 294049)
- date added to LUP
- 2016-04-01 16:34:16
- date last changed
- 2022-01-28 20:34:08
@article{06da6959-ea37-4b66-b805-0b5f2fbba17c, abstract = {{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.}}, author = {{Björklund, Andreas and Husfeldt, Thore}}, issn = {{0097-5397}}, keywords = {{longest path; approximation algorithms; graph algorithms}}, language = {{eng}}, number = {{6}}, pages = {{1395--1402}}, publisher = {{Society for Industrial and Applied Mathematics}}, series = {{SIAM Journal on Computing}}, title = {{Finding a path of superlogarithmic length}}, url = {{http://dx.doi.org/10.1137/S0097539702416761}}, doi = {{10.1137/S0097539702416761}}, volume = {{32}}, year = {{2003}}, }