Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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 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
and
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
host publication
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
conference location
Malaga, Spain
conference dates
2002-07-08 - 2002-07-13
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
2016-04-04 11:05:04
date last changed
2025-04-04 15:30:48
@inproceedings{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}},
  booktitle    = {{Automata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 8-13, 2002 : proceedings}},
  isbn         = {{3540438645}},
  keywords     = {{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    = {{Springer}},
  title        = {{Finding a path of superlogarithmic length}},
  url          = {{https://lup.lub.lu.se/search/files/5690803/623761.pdf}},
  volume       = {{LNCS 2380}},
  year         = {{2002}},
}