DIMACS TR: 93-81
Fast Parallel Algorithms for Finding Hamiltonian Cycles and
Trees in Graphs
Author: Gabor Sarkozy
ABSTRACT
Suppose 0 < delta < 1 is given. We call a graph, G, on n vertices a delta-
Posa graph if
its degree sequence d_1 <= d_2 <= ... <= d_n satisfies:
for 1<= k <= n,
d_k >= min { k + delta n, n/2 }. An NC^4-algorithm is presented which
accepts
as input a
delta-Posa graph and produces a Hamiltonian cycle in G as an
output. This is a significant improvement on the previous best
NC-algorithm for the problem , which finds a Hamiltonian cycle only
in Dirac graphs ( delta (G) >= n/2 where delta (G) is
the minimum degree in G ). The difficulty of the problem is
indicated by the fact , that if alpha < 1/2,
the Hamiltonian cycle problem restricted to alpha-dense graphs (
delta (G) >= alpha n ) becomes NP-complete. A related
NC^4-algorithm is also presented which accepts as inputs a bounded
degree tree T on n vertices, and a graph G on also n vertices
with delta (G) >= ( 1/2 + epsilon ) n, and it
finds a copy of T in G.
Paper only.
DIMACS Home Page