ダウンロード数: 269
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
s13160-012-0072-2.pdf | 115 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Takazawa, Kenjiro | en |
dc.contributor.alternative | 高澤, 兼二郎 | ja |
dc.date.accessioned | 2013-01-10T01:36:21Z | - |
dc.date.available | 2013-01-10T01:36:21Z | - |
dc.date.issued | 2012-10 | - |
dc.identifier.issn | 0916-7005 | - |
dc.identifier.uri | http://hdl.handle.net/2433/167968 | - |
dc.description.abstract | 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. | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Springer Japan | en |
dc.rights | The final publication is available at www.springerlink.com | en |
dc.rights | この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 | ja |
dc.rights | This is not the published version. Please cite only the published version. | en |
dc.subject | Shortest bibranching | en |
dc.subject | Arborescence | en |
dc.subject | Valuated matroid intersection | en |
dc.subject | Discrete convex function | en |
dc.title | Shortest bibranchings and valuated matroid intersection | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.ncid | AA10799861 | - |
dc.identifier.jtitle | Japan Journal of Industrial and Applied Mathematics | en |
dc.identifier.volume | 29 | - |
dc.identifier.issue | 3 | - |
dc.identifier.spage | 561 | - |
dc.identifier.epage | 573 | - |
dc.relation.doi | 10.1007/s13160-012-0072-2 | - |
dc.textversion | author | - |
dcterms.accessRights | open access | - |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。