Fast Parallel Algorithms for Finding Hamiltonian Paths and Cycles in a Tournament

Abstract

A tournament is a digraph T=( V, E) in which, for every pair of vertices, u & v, exactly one of (u, v), (v, u) is in E. Two classical theorems about tournaments are that every tournament has a Hamiltonian path, and every strongly connected tournament has a Hamiltonian cycle. Furthermore, it is known how to find these in polynomial time. In this paper we discuss the parallel complexity of these problems. Our main result is that constructing a Hamiltonian path in a general tournament and a Hamiltonian cycle in a strongly connected tournament are both in NC. In addition, we give an NC algorithm for finding a Hamiltonian path with one fixed endpoint. In finding fast parallel algorithms, we also obtain new proofs for the theorems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1986
Accession Number
ADA619387

Entities

People

  • Danny Soroker

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • California
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Contracts
  • Information Operations
  • Mathematics
  • Observation
  • Polynomials
  • Standards
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.