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

Publiceringsår

2002

Språk

Engelska

Sidor

985-992

Publikation/Tidskrift/Serie

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

Volym

LNCS 2380

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Computer Science

Nyckelord

  • 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/Övrigt

  • ISBN: 3540438645