Minimum diameter and cycle-diameter orientations on planar graphs

Details Minimum diameter and cycle-diameter orientations on planar graphs Minimum diameter and cycle-diameter orientations on planar graphs

2011-05-24

arxiv.org/abs/1105.4770v1

Computer Science

Discrete Mathematics

Scientific paper

Let G be an edge weighted undirected graph. For every pair of nodes consider the shortest cycle containing these nodes in G. The cycle diameter of G is the maximum length of a cycle in this set. Let H be a directed graph obtained by directing the edges of G. The cycle diameter of H is similarly defined except for that cycles are replaced by directed closed walks. Is there always an orientation H of G whose cycle diameter is bounded by a constant times the cycle diameter of G? We prove this property for planar graphs. These results have implications on the problem of approximating an orientation with minimum diameter

Affiliated with

Also associated with

No associations

Rating

Minimum diameter and cycle-diameter orientations on planar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum diameter and cycle-diameter orientations on planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum diameter and cycle-diameter orientations on planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-515912