Series-parallel orientations preserving the cycle-radius |
| |
Authors: | Nili Guttmann-Beck Refael Hassin |
| |
Affiliation: | 1. Department of Computer Science, The Academic College of Tel-Aviv Yaffo, Yaffo, Israel;2. Department of Statistics and Operations Research, Tel-Aviv University, Tel-Aviv 69978, Israel |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|