Finding a path of superlogarithmic length

Andreas Björklund, Thore Husfeldt

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingResearchpeer-review

3 Citations (SciVal)
138 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationAutomata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 8-13, 2002 : proceedings
PublisherSpringer
Pages985-992
VolumeLNCS 2380
ISBN (Print)3540438645
Publication statusPublished - 2002
EventProceedings of 29th International Colloquium on Automata, Languages and Programming - Malaga, Spain
Duration: 2002 Jul 82002 Jul 13

Publication series

Name
VolumeLNCS 2380

Conference

ConferenceProceedings of 29th International Colloquium on Automata, Languages and Programming
Country/TerritorySpain
CityMalaga
Period2002/07/082002/07/13

Subject classification (UKÄ)

  • Computer Science

Keywords

  • computational complexity
  • graph theory
  • superlogarithmic length path finding
  • undirected graph
  • polynomial-time algorithm
  • performance ratio
  • graph vertices
  • longest path problem

Fingerprint

Dive into the research topics of 'Finding a path of superlogarithmic length'. Together they form a unique fingerprint.

Cite this