Finding a path of superlogarithmic length

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

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

computational complexity

graph theory

superlogarithmic length path finding

undirected graph

polynomial-time algorithm

performance ratio

graph vertices

longest path problem

Publikations- och innehållstyp

kon (ämneskategori)

ref (ämneskategori)