Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Finding a path of superlogarithmic length

In English

Författare

Summary, in English

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.

Publiceringsår

2003

Språk

Engelska

Sidor

1395-1402

Publikation/Tidskrift/Serie

SIAM Journal on Computing

Volym

32

Issue

6

Dokumenttyp

Artikel i tidskrift

Förlag

Society for Industrial and Applied Mathematics

Ämne

  • Computer Science

Nyckelord

  • longest path
  • approximation algorithms
  • graph algorithms

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 0097-5397