首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号