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:
http://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
 SIAM Publications
 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
 20070824 11:00:16
 date last changed
 20180610 04:40:42
@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}, keyword = {longest path,approximation algorithms,graph algorithms}, language = {eng}, number = {6}, pages = {13951402}, publisher = {SIAM Publications}, series = {SIAM Journal on Computing}, title = {Finding a path of superlogarithmic length}, url = {http://dx.doi.org/10.1137/S0097539702416761}, volume = {32}, year = {2003}, }