文章基本信息

标题：On Properties of a Set of Global Roundings Associated with Clique Connection of Graphs
本地全文：下载
作者：Tomonori ISHIKAWA ; Ken-ich KAWARABAYASHI ; Takeshi TOKUYAMA 等
期刊名称：Interdisciplinary Information Sciences
印刷版ISSN：1340-9050
电子版ISSN：1347-6157
出版年度：2004
卷号：10
期号：2
页码：159-163
DOI：10.4036/iis.2004.159
出版社：The Editorial Committee of the Interdisciplinary Information Sciences
摘要：Given a connected weighted graph G =( V , E ), we consider a hypergraph H ( G )=( V , F ( G )) corresponding to the set of all shortest paths in G . For a given real assignment a on V satisfying 0≤ a ( v )≤1, a global rounding α with respect to H ( G ) is a binary assignment satisfying that |∑_{v ∈ F} a ( v )−α( v )|<1 for every F ∈ F ( G ). Asano et al. [3] conjectured that there are at most | V |+1 global roundings for H ( G ). In this paper, we present monotone properties on size and affine corank of a set of global roundings under a clique connection operation.