Finding a path of superlogarithmic length

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

Abstract

We consider the problem of finding a long, simple path in an undirected graph. We present a polynomial-time algorithm that finds a path of length Omega((log L/log log L)(2)), where L denotes the length of the longest simple path in the graph. This establishes the performance ratio O(n( log log n/log n)(2)) for the longest path problem, where n denotes the number of vertices in the graph.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Sidor (från-till)1395-1402
TidskriftSIAM Journal on Computing
Volym32
Utgivningsnummer6
StatusPublished - 2003
PublikationskategoriForskning
Peer review utfördJa