Finding a path of superlogarithmic length
(2002) Proceedings of 29th International Colloquium on Automata, Languages and Programming LNCS 2380. p.985992 Abstract
 We consider the problem of nding a long, simple path in anundirected graph.W e present a polynomialtime algorithm that ndsa path of length (log L/ log log L)2, where L denotes the length ofthe longest simple path in the graph.This establishes the performanceratio OV (log log V / log V )2 for the Longest Path problem, whereV denotes the graphs vertices.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/526604
 author
 Björklund, Andreas ^{LU} and Husfeldt, Thore ^{LU}
 organization
 publishing date
 2002
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 computational complexity, graph theory, superlogarithmic length path finding, undirected graph, polynomialtime algorithm, performance ratio, graph vertices, longest path problem
 host publication
 Automata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 813, 2002 : proceedings
 volume
 LNCS 2380
 pages
 985  992
 publisher
 Springer
 conference name
 Proceedings of 29th International Colloquium on Automata, Languages and Programming
 conference location
 Malaga, Spain
 conference dates
 20020708  20020713
 external identifiers

 wos:000180069500084
 scopus:1842539952
 ISBN
 3540438645
 language
 English
 LU publication?
 yes
 id
 a503c905dbed490a8de2106f0ce8ae3b (old id 526604)
 alternative location
 http://link.springer.de/link/service/series/0558/papers/2380/23800985.pdf
 date added to LUP
 20160404 11:05:04
 date last changed
 20220408 06:42:12
@inproceedings{a503c905dbed490a8de2106f0ce8ae3b, abstract = {{We consider the problem of nding a long, simple path in anundirected graph.W e present a polynomialtime algorithm that ndsa path of length (log L/ log log L)2, where L denotes the length ofthe longest simple path in the graph.This establishes the performanceratio OV (log log V / log V )2 for the Longest Path problem, whereV denotes the graphs vertices.}}, author = {{Björklund, Andreas and Husfeldt, Thore}}, booktitle = {{Automata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 813, 2002 : proceedings}}, isbn = {{3540438645}}, keywords = {{computational complexity; graph theory; superlogarithmic length path finding; undirected graph; polynomialtime algorithm; performance ratio; graph vertices; longest path problem}}, language = {{eng}}, pages = {{985992}}, publisher = {{Springer}}, title = {{Finding a path of superlogarithmic length}}, url = {{https://lup.lub.lu.se/search/files/5690803/623761.pdf}}, volume = {{LNCS 2380}}, year = {{2002}}, }