Finding a path of superlogarithmic length
(2003) In SIAM Journal on Computing 32(6). p.13951402 Abstract
 We consider the problem of finding a long, simple path in an undirected graph. We present a polynomialtime 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
 00975397
 DOI
 10.1137/S0097539702416761
 language
 English
 LU publication?
 yes
 id
 06da6959ea374b66b8050b5f2fbba17c (old id 294049)
 date added to LUP
 20160401 16:34:16
 date last changed
 20211006 03:04:17
@article{06da6959ea374b66b8050b5f2fbba17c, abstract = {We consider the problem of finding a long, simple path in an undirected graph. We present a polynomialtime 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 = {00975397}, language = {eng}, number = {6}, pages = {13951402}, 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}, }