Meny

Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Approximating Longest Path

Författare:
Publiceringsår: 2003
Språk: Engelska
Sidor: 25
Dokumenttyp: Licentiatavhandling

Sammanfattning

We investigate the computational hardness of approximating the longest path and the longest cycle in undirected and directed graphs on n vertices. We show that
* in any expander graph, we can find (n) long paths in polynomial time.
* there is an algorithm that finds a path of length (log2 L/ log log L) in any undirected graph having a path of length L, in polynomial time.
* there is an algorithm that finds a path of length (log2 n/ log log n) in any Hamiltonian directed graph of constant bounded outdegree, in polynomial time.
* there cannot be an algorithm finding paths of length (n ) for any constant > 0 in a Hamiltonian directed graph of bounded outdegree in polynomial time, unless P = NP.
* there cannot be an algorithm finding paths of length (log2+ n), or cycles of length (log1+ n) for any constant > 0 in a Hamiltonian directed graph of constant bounded outdegree in polynomial time, unless 3-Sat can be solved in subexponential time.

Disputation

Nyckelord

  • Mathematics and Statistics
  • Technology and Engineering

Övriga

  • Thore Husfeldt

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen