Du är här

Finding a path of superlogarithmic length

Publiceringsår: 2002
Språk: Engelska
Sidor: 985-992
Publikation/Tidskrift/Serie: Automata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 8-13, 2002 : proceedings
Volym: LNCS 2380
Dokumenttyp: Konferensbidrag
Förlag: Springer-Verlag

Sammanfattning

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.

Disputation

Nyckelord

  • Mathematics and Statistics
  • Technology and Engineering
  • computational complexity
  • graph theory
  • superlogarithmic length path finding
  • undirected graph
  • polynomial-time algorithm
  • performance ratio
  • graph vertices
  • longest path problem

Övriga

Proceedings of 29th International Colloquium on Automata, Languages and Programming
8-13 July 2002
Malaga, Spain
Published
Yes
  • ISBN: 3540438645

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

LERU logotype U21 logotype

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen