WEKO3
アイテム
グラフ及び領域空間に関する大域丸めの幾何学的性質について
https://ipsj.ixsq.nii.ac.jp/records/31854
https://ipsj.ixsq.nii.ac.jp/records/318543811410f-cc6d-45d9-9e72-ce02fd9199bf
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2004 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2004-05-21 | |||||||
タイトル | ||||||||
タイトル | グラフ及び領域空間に関する大域丸めの幾何学的性質について | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | On Geometric Structure of Global Roundings for Graphs and Range Spaces | |||||||
言語 | ||||||||
言語 | eng | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
北陸先端科学技術大学院大学 | ||||||||
著者所属 | ||||||||
京都大学 | ||||||||
著者所属 | ||||||||
明治大学 | ||||||||
著者所属 | ||||||||
東北大学 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
JAIST | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Kyoto University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Meiji University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Tohoku University | ||||||||
著者名 |
浅野, 哲夫
× 浅野, 哲夫
|
|||||||
著者名(英) |
Tetsuo, Asano
× Tetsuo, Asano
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | ハイパーグラフH=(V F) と[0 1]-値ベクトルa∈[0 1]^Vが与えられた時、Hに関するaの大域丸めとは二値ベクトルα∈{0 1}Vで、全てのハイパーエッジFに対して|Σv∈F(a(v)?α(v))|<1が成り立つものの事を言う。本論文では、aの大域丸め全体の集合の幾何学的及び組合せ的性質を考察する。 具体的には、ハイパーグラフが最短路公理を満たすとき、大域丸めの集合が単体をなすことを予想し、幾何的な領域空間や、直並列グラフの最短路ハイパーグラフに対してこの予想を示す。 | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | Given a hypergraph H=(V,F) and a [0,1]-valued vector a ∈[0,1]V, its global rounding is a binary (i.e.,{0,1}-valued) vector α∈{0,1}V such that |Σv∈F (a(v)?α(v))|<1 holds for each F∈F. We study geometric (or combinatorial) structure of the set of global roundings of a using the notion of compatible set with respect to the discrepancy distance. We conjecture that the set of global roundings forms a simplex if the hypergraph satisfies “shortest-path” axioms, and prove it for some special cases including some geometric range spaces and the shortest path hypergraph of a series-parallel graph. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 2004, 号 52(2004-AL-095), p. 35-42, 発行日 2004-05-21 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |