Advanced

Finding a path of superlogarithmic length

Björklund, Andreas LU and Husfeldt, Thore LU (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:
author
organization
publishing date
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
SIAM Publications
external identifiers
  • wos:000186766600001
  • scopus:0942288266
ISSN
0097-5397
DOI
language
English
LU publication?
yes
id
06da6959-ea37-4b66-b805-0b5f2fbba17c (old id 294049)
date added to LUP
2007-08-24 11:00:16
date last changed
2018-06-10 04:40:42
@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},
  keyword      = {longest path,approximation algorithms,graph algorithms},
  language     = {eng},
  number       = {6},
  pages        = {1395--1402},
  publisher    = {SIAM Publications},
  series       = {SIAM Journal on Computing},
  title        = {Finding a path of superlogarithmic length},
  url          = {http://dx.doi.org/},
  volume       = {32},
  year         = {2003},
}