Accession Number:

ADA018426

Title:

Distances in Orientations of Graphs.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1975-08-01

Pagination or Media Count:

28.0

Abstract:

The authors prove that there is a function hk such that every undirected graph G admits an orientation H with the following property if an edge uv belongs to a cycle of length k in G then uv or vu belongs to a directed cycle of length at most hk in H. Next, it is shown that every undirected bridgeless graph of radius r admits an orientation of radius at most r sup 2 r, and this bound is best possible. The same problem is considered with radius replaced by diameter. Finally, it is shown that the problem of deciding whether an undirected graph admits an orientation of diameter resp. radius two belongs to a class of problems called NP-hard.

Subject Categories:

  • Theoretical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE