Advanced

Finding a path of superlogarithmic length

Björklund, Andreas LU and Husfeldt, Thore LU (2002) Proceedings of 29th International Colloquium on Automata, Languages and Programming In Automata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 8-13, 2002 : proceedings LNCS 2380. p.985-992
Abstract
We consider the problem of nding a long, simple path in anundirected graph.W e present a polynomial-time 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 O|V |(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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
computational complexity, graph theory, superlogarithmic length path finding, undirected graph, polynomial-time algorithm, performance ratio, graph vertices, longest path problem
in
Automata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 8-13, 2002 : proceedings
volume
LNCS 2380
pages
985 - 992
publisher
Springer
conference name
Proceedings of 29th International Colloquium on Automata, Languages and Programming
external identifiers
  • WOS:000180069500084
  • Scopus:1842539952
ISBN
3540438645
language
English
LU publication?
yes
id
a503c905-dbed-490a-8de2-106f0ce8ae3b (old id 526604)
alternative location
http://link.springer.de/link/service/series/0558/papers/2380/23800985.pdf
date added to LUP
2007-09-13 12:26:10
date last changed
2016-10-13 04:43:51
@misc{a503c905-dbed-490a-8de2-106f0ce8ae3b,
  abstract     = {We consider the problem of nding a long, simple path in anundirected graph.W e present a polynomial-time 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 O|V |(log log |V |/ log |V |)2 for the Longest Path problem, whereV denotes the graphs vertices.},
  author       = {Björklund, Andreas and Husfeldt, Thore},
  isbn         = {3540438645},
  keyword      = {computational complexity,graph theory,superlogarithmic length path finding,undirected graph,polynomial-time algorithm,performance ratio,graph vertices,longest path problem},
  language     = {eng},
  pages        = {985--992},
  publisher    = {ARRAY(0x92e4de0)},
  series       = {Automata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 8-13, 2002 : proceedings},
  title        = {Finding a path of superlogarithmic length},
  volume       = {LNCS 2380},
  year         = {2002},
}