ダウンロード数: 269
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
s13160-012-0072-2.pdf | 115 kB | Adobe PDF | 見る/開く |
タイトル: | Shortest bibranchings and valuated matroid intersection |
著者: | Takazawa, Kenjiro |
著者名の別形: | 高澤, 兼二郎 |
キーワード: | Shortest bibranching Arborescence Valuated matroid intersection Discrete convex function |
発行日: | Oct-2012 |
出版者: | Springer Japan |
誌名: | Japan Journal of Industrial and Applied Mathematics |
巻: | 29 |
号: | 3 |
開始ページ: | 561 |
終了ページ: | 573 |
抄録: | For a digraph D = (V, A) and a partition {S, T} of V, an arc set B⊆A is called an S−T if each vertex in T is reachable from S and each vertex in S reaches T in the subgraph (V, B). Bibranchings commonly generalize bipartite edge covers and arborescences. A totally dual integral linear system determining the S−T polytope is provided by Schrijver, and the shortest S−T problem, whose objective is to find an S−T of minimum total arc weight, can be solved in polynomial time by the ellipsoid method or a faster combinatorial algorithm due to Keijsper and Pendavingh. The valuated matroid intersection problem, introduced by Murota, is a weighted generalization of the independent matching problem, including the independent assignment problem and the weighted matroid intersection problem. The valuated matroid intersection problem can be solved efficiently with polynomially many value oracles by extending classical combinatorial algorithms for the weighted matroid intersection problem. In this paper, we show that the shortest S−T problem is polynomially reducible to the valuated matroid intersection problem. This reduction suggests one answer to why the shortest S−T problem is tractable, and implies new combinatorial algorithms for the shortest S−T problem based on the valuated matroid intersection algorithm, where a value oracle corresponds to computing a minimum-weight arborescence. |
著作権等: | The final publication is available at www.springerlink.com この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 This is not the published version. Please cite only the published version. |
URI: | http://hdl.handle.net/2433/167968 |
DOI(出版社版): | 10.1007/s13160-012-0072-2 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。