Enumerating global roundings of an outerplanar graph

Nadia Takki-Chebihi, Takeshi Tokuyama

研究成果: Article査読

5 被引用数 (Scopus)


Given a connected weighted graph G = (V, E), we consider a hypergraph H G = (V, P 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∈Fa(v)-α(v)| < 1 for every F ∈ P G. Asano et al [1] conjectured that there are at most |V|+1 global roundings for H G. In this paper, we prove that the conjecture holds if G is an outerplanar graph. Moreover, we give a polynomial time algorithm for enumerating all the global roundings of an outerplanar graph.

ジャーナルLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
出版ステータスPublished - 2003 12月 1

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • コンピュータ サイエンス(全般)


「Enumerating global roundings of an outerplanar graph」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。