ダウンロード数: 251
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
s10107-010-0397-z.pdf | 123.22 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Takazawa, Kenjiro | en |
dc.contributor.alternative | 高澤, 兼二郎 | ja |
dc.date.accessioned | 2012-04-11T07:53:01Z | - |
dc.date.available | 2012-04-11T07:53:01Z | - |
dc.date.issued | 2012-04 | - |
dc.identifier.issn | 0025-5610 | - |
dc.identifier.uri | http://hdl.handle.net/2433/154867 | - |
dc.description.abstract | An even factor in a digraph is a vertex-disjoint collection of directed cycles of even length and directed paths. An even factor is called independent if it satisfies a certain matroid constraint. The problem of finding an independent even factor of maximum size is a common generalization of the nonbipartite matching and matroid intersection problems. In this paper, we present a primal-dual algorithm for the weighted independent even factor problem in odd-cycle-symmetric weighted digraphs. Cunningham and Geelen have shown that this problem is solvable via valuated matroid intersection. Their method yields a combinatorial algorithm running in O(n [3] γ + n [6] m) time, where n and m are the number of vertices and edges, respectively, and γ is the time for an independence test. In contrast, combining the weighted even factor and independent even factor algorithms, our algorithm works more directly and runs in O(n [4] γ + n [5]) time. The algorithm is fully combinatorial, and thus provides a new dual integrality theorem which commonly extends the total dual integrality theorems for matching and matroid intersection. | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Springer and Mathematical Optimization Society | 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 | Independent even factor | en |
dc.subject | Combinatorial algorithm | en |
dc.subject | Dual integrality | en |
dc.subject | Nonbipartite matching | en |
dc.subject | Matroid intersection | en |
dc.title | A weighted independent even factor algorithm | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.ncid | AA00295781 | - |
dc.identifier.jtitle | Mathematical Programming | en |
dc.identifier.volume | 132 | - |
dc.identifier.issue | 1-2 | - |
dc.identifier.spage | 261 | - |
dc.identifier.epage | 276 | - |
dc.relation.doi | 10.1007/s10107-010-0397-z | - |
dc.textversion | author | - |
dcterms.accessRights | open access | - |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。