کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428596 | 686830 | 2012 | 8 صفحه PDF | دانلود رایگان |
Let G be an undirected 2-edge connected graph with nonnegative edge weights and a distinguished vertex z. For every node consider the shortest cycle containing this node and z in G. The cycle-radius 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-radius of H is similarly defined except that cycles are replaced by directed closed walks. We prove that there exists for every nonnegative edge weight function an orientation H of G whose cycle-radius equals that of G if and only if G is series-parallel.
► We define the cycle-radius of a graph and use it as a measure for the quality of an orientation of the graph.
► This concept is useful when orienting an undirected graph while minimizing the resulting diameter.
► It also provides a new characterization of series-parallel graphs.
Journal: Information Processing Letters - Volume 112, Issue 4, 15 February 2012, Pages 153–160