Finding a path of superlogarithmic length

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Titel på värdpublikationAutomata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 8-13, 2002 : proceedings
FörlagSpringer
Sidor985-992
VolymLNCS 2380
ISBN (tryckt)3540438645
StatusPublished - 2002
PublikationskategoriForskning
Peer review utfördJa
EvenemangProceedings of 29th International Colloquium on Automata, Languages and Programming - Malaga, Spanien
Varaktighet: 2002 jul 82002 jul 13

Publikationsserier

Namn
VolymLNCS 2380

Konferens

KonferensProceedings of 29th International Colloquium on Automata, Languages and Programming
LandSpanien
OrtMalaga
Period2002/07/082002/07/13

Nedladdningar

Ingen tillgänglig data