Du är här

Finding a path of superlogarithmic length

Publiceringsår: 2003
Språk: Engelska
Sidor: 1395-1402
Publikation/Tidskrift/Serie: SIAM Journal on Computing
Volym: 32
Nummer: 6
Dokumenttyp: Artikel
Förlag: SIAM Publications

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering
  • longest path
  • approximation algorithms
  • graph algorithms

Övrigt

Published
Yes
  • ISSN: 0097-5397

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

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

LERU logo U21 logo