最大重み極小セパレータ問題について

• Item type: SIG Technical Reports(1)
• 公開日: 2016-06-17
• タイトル: 最大重み極小セパレータ問題について
• タイトル / 言語: en
• タイトル: On the Maximum Weight Minimal Separator
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Economic Engineering, Kyushu University
• 著者所属: Department of Computing Science Algorithmic Systems, Utrecht University
• 著者所属: Department of Computing Science Algorithmic Systems, Utrecht University
• 著者所属: Department of Economic Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Department of Economic Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Department of Computing Science Algorithmic Systems, Utrecht University
• 著者所属(英): en
• 著者所属(英): Department of Computing Science Algorithmic Systems, Utrecht University
• 著者所属(英): en
• 著者所属(英): Department of Economic Engineering, Kyushu University
• 著者名: 土中, 哲秀; Bodlaender, Hans L.; Zanden, T.C. van der; 小野, 廣隆
• 著者名(英): Tesshu, Hanaka; Hans, L. Bodlaender; T.C., van der Zanden; Hirotaka, Ono
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 無向連結グラフ G = (V,E) において，2 点 s,t が与えられたとき，s と t を分離する点部分集合を s-t セパレータという．特に，任意の真部分集合が s-t セパレータではないものを極小 s-t セパレータという．本研究では，点重み付きグラフに対して，重み最大の極小 s-t セパレータを発見する問題について考察する．まずこの問題が NP 困難であることを示した上で，木幅が tw 以下のグラフに対して，O*(9tw・W)- 時間で重み W の極小 s-t セパレータが存在するかどうかを判定する乱択アルゴリズムを提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given an undirected and connected graph G = (V,E) and two vertices s, t ∈ V, a vertex subset S which separates s and t is called s-t separator. Additionally, S is called minimal s-t separator if no proper set of S separates s and t. In this pater, we consider finding a minimal s-t separator with maximum weight on a vertex-weighted graph. We firstly prove this problem is NP-hard. Then we propose an O*(9tw・W)-randomized algorithm to determine whether there exists a minimal s-t separator with weight W on a graph with bounded treewidth.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2016-AL-158, 号 12, p. 1-7, 発行日 2016-06-17
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会