論文

査読有り
2014年

OPTIMAL MATCHING FORESTS AND VALUATED DELTA-MATROIDS

SIAM JOURNAL ON DISCRETE MATHEMATICS
  • Kenjiro Takazawa

28
1
開始ページ
445
終了ページ
467
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1137/110827661
出版者・発行元
SIAM PUBLICATIONS

The matching forest problem in mixed graphs is a common generalization of the matching problem in undirected graphs and the branching problem in directed graphs. Giles presented an O(n(2)m)-time algorithm for finding a maximum-weight matching forest, where n is the number of vertices and m is that of edges, and a linear system describing the matching forest polytope. Later, Schrijver proved total dual integrality of the linear system. In the present paper, we reveal another nice property of matching forests: the degree sequences of the matching forests in any mixed graph form a delta-matroid, and the weighted matching forests induce a valuated delta-matroid. We remark that the delta-matroid is not necessarily even, and the valuated delta-matroid induced by weighted matching forests slightly generalizes the well-known notion of Dress and Wenzel's valuated delta-matroids. By focusing on the delta-matroid structure and reviewing Giles' algorithm, we design a simpler O(n(2)m)-time algorithm for the weighted matching forest problem. By incorporating Gabow's method for the weighted matching problem into Giles' algorithm, we also present a faster algorithm for the weighted matching forest problem running in O(n(3))-time, which improves upon the previous best complexity of O(n(2)m).

リンク情報
DOI
https://doi.org/10.1137/110827661
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000333685700031&DestApp=WOS_CPL
ID情報
  • DOI : 10.1137/110827661
  • ISSN : 0895-4801
  • eISSN : 1095-7146
  • Web of Science ID : WOS:000333685700031

エクスポート
BibTeX RIS