Enumerating Global Roundings of an Outerplanar Graph
Enumerating Global Roundings of an Outerplanar Graph
复制标题
枚举外平面图的全局舍入
DOI：
10.1007/978-3-540-24587-2_44
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
T. Tokuyama
中科院分区：
文献类型：
--
作者：
Nadia Takki;T. Tokuyama
给定一个连通赋权图G =（V，E），我们考虑一个对应于G中所有最短路的超图.对于一个给定的真实的赋值v，满足0 ≤a（v）≤ 1，关于的全局舍入α是一个二元赋值，满足|∑v∈Fa（v）−α（v）|< 1对于每一个。Asano等人[1]指出，|V| +1全球销售额。本文证明了当G是外可平面图时，猜想成立。此外，我们还给出了一个多项式时间算法来计算外平面图的所有全局图。
Given a connected weighted graphG= (V,E), we consider a hypergraphcorresponding to the set of all shortest paths inG. For a given real assignmentaonVsatisfying 0 ≤a(v) ≤ 1, a global roundingαwith respect tois a binary assignment satisfying that | ∑v∈Fa(v) −α(v)| < 1 for every. Asano et al [1] conjectured that there are at most |V|+1 global roundings for. In this paper, we prove that the conjecture holds ifGis an outerplanar graph. Moreover, we give a polynomial time algorithm for enumerating all the global roundings of an outerplanar graph.
DOI：
--
发表时间：
2005
期刊：
Theoretical Computer Science Vol.331, No.1
影响因子：
--
作者：
K.Sadakane;N.Takki-Chebihi;T.Tokuyama
通讯作者：
T.Tokuyama
DOI：
--
发表时间：
2004
期刊：
Theoretical Computer Science 325
影响因子：
--
作者：
T.Asano;N.Katoh;H.Tamaki;T.Tokuyama
通讯作者：
T.Tokuyama