WEKO3
アイテム
グラフに関する丸め問題:外平面グラフの場合
https://ipsj.ixsq.nii.ac.jp/records/31922
https://ipsj.ixsq.nii.ac.jp/records/31922270af0e5-be4c-45f9-b149-77845667be6d
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2003 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2003-05-23 | |||||||
タイトル | ||||||||
タイトル | グラフに関する丸め問題:外平面グラフの場合 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Rounding Problem on Graphs: Case of Outerplanar Graphs | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
東北大学大学院情報科学研究科 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
GSIS, Tohoku University | ||||||||
著者名 |
徳山, 豪
× 徳山, 豪
|
|||||||
著者名(英) |
Takeshi, Tokuyama
× Takeshi, Tokuyama
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 頂点に実数値の重みを持つグラフGが与えられた時、これらの重みを整数値に丸めることを考える。このとき、全ての最短路の上での重み和が入力の実数重みの和の丸めになっているとき、この丸めを大域丸め(global rounding) と言う。任意のn頂点グラフに対し、大域丸めはn+1個以下しかないと予想されている。本論文では外平面グラフに対してこの予想を示し、かつ、全ての大域丸めを列挙する多項式時間アルゴリズムを与える。 | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | Given a connected weighted graph G = (V, E) and a given real-valued assignment a on V satisfying 0 < a(v) < 1, a global rounding α with respect to G is a binary assignment satisfying that |Σ{v ∈ P} a(v) - α(v) | < 1 for every shortest path P in G. Asano et al [1] conjectured that there are at most |V|+1 global roundings for G. We prove that the conjecture holds if G is an outerplanar graph. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 2003, 号 53(2003-AL-090), p. 65-72, 発行日 2003-05-23 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |