Distances in Orientations of Graphs.
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Theoretical Mathematics
- Operations Research