Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
and
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
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
2025-10-14 09:19:37
@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}},
}