The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Finding a path of superlogarithmic length

På svenska

Author

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.

Publishing year

2003

Language

English

Pages

1395-1402

Publication/Series

SIAM Journal on Computing

Volume

32

Issue

6

Document type

Journal article

Publisher

Society for Industrial and Applied Mathematics

Topic

  • Computer Science

Keywords

  • longest path
  • approximation algorithms
  • graph algorithms

Status

Published

ISBN/ISSN/Other

  • ISSN: 0097-5397