| 講演名 | 2003/11/18 ハイパーグラフの重み付き横断 , /, 牧野 和久, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 我々は,有限ハイパグラフの横断の一般化である重み付き横断を考察する.入力ハイパーグラフAの各枝に割り当てられた非負の重みベクトルと非負の閾ベクトルが与えられたとき,重み付き横断を交わりをもたないAの枝の重み和が閾ベクトル以下である極小な点集合と定義する.この重み付き横断は,部分横断,多重横断の一般化である.本論文では,すべての重み付き横断から成るハイパーグラフが双対制限されている.すなわち,その横断ハイパーグラフのサイズが,重み付き横断数と入力のハイパーグラフのサイズの多項式であることを示す.また,すべてのすべての重み付き横断を列挙する問題を別のハイパーグラフのすべての横断を列挙する問題,すなわち,有名なハイパーグラフ双対化問題に多項式時間で帰着できることを示す.系として,すべての重み付き横断の列挙が逐次擬多項式時間で可能であることも示す. |
| 抄録(英) | We consider a generalization of the notion of transversal to a finite hypergraph, so called weighted transversals. Given a non-negative weight vector assigned to each hyperedge of an input hypergraph A and a non-negative threshold vector, we define a weighted transversal as a minimal vertex set which intersects all the hyperedges of A except for a sub-family of total weight not exceeding the given threshold vector. Weighted transversals generalize partial and multiple transversals. We show that the hypergraph of all weighted transversals is dual-bounded, i. e., the size of its transversal hypergraph is polynomial in the number of weighted transversals and the size of the input hypergraph. We also prove that the problem of generating all weighted transversals for a given hypergraph is polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i. e., to the well-known hypergraph dualization problem. As a corollary, we obtain an incremental quasi-polynomial-time algorithm for generating all weighted transversals for a given hypergraph. |
| キーワード(和) | 双対化 / 交差不等式 / 多重横断 / 部分横断 |
| キーワード(英) | dualization / intersection inequality / multiple transversal / partial transversal |
| 資料番号 | COMP2003-56 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2003/11/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | ハイパーグラフの重み付き横断 |
| サブタイトル（和） | |
| タイトル（英） | Weighted Transversals of a Hypergraph |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 双対化 / dualization |
| キーワード(2)（和/英） | 交差不等式 / intersection inequality |
| キーワード(3)（和/英） | 多重横断 / multiple transversal |
| キーワード(4)（和/英） | 部分横断 / partial transversal |
| 第 1 著者 氏名（和/英） | / Endre Boros |
| 第 1 著者 所属（和/英） | RUTCOR, Rutgers University |
| 第 2 著者 氏名（和/英） | / / Vladimir Gurivich |
| 第 2 著者 所属（和/英） | / RUTCOR, Rutgers University |
| 第 3 著者 氏名（和/英） | 牧野 和久 / Leonid Khachiyan |
| 第 3 著者 所属（和/英） | 大阪大学大学院基礎工学研究科社会システム数理領域 Department of Computer Science, Rutgers University |
| 発表年月日 | 2003/11/18 |
| 資料番号 | COMP2003-56 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 468 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |