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 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.

Publishing year

2002

Language

English

Pages

985-992

Publication/Series

Automata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 8-13, 2002 : proceedings

Volume

LNCS 2380

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Keywords

  • computational complexity
  • graph theory
  • superlogarithmic length path finding
  • undirected graph
  • polynomial-time algorithm
  • performance ratio
  • graph vertices
  • longest path problem

Conference name

Proceedings of 29th International Colloquium on Automata, Languages and Programming

Conference date

2002-07-08 - 2002-07-13

Conference place

Malaga, Spain

Status

Published

ISBN/ISSN/Other

  • ISBN: 3540438645