Optimal matching forests and valuated delta-matroids,
Optimal matching forests and valuated delta-matroids,
复制标题
最佳匹配森林和评估的δ拟阵，
DOI：
10.1137/110827661
复制
发表时间：
2014
影响因子：
0.8
通讯作者：
Kenjiro Takazawa
中科院分区：
文献类型：
--
作者：
Yoshida LM;Suzuki M;Thiem VD;Smith WP;Tsuzuki A;Huong VT;Takahashi K;Miyakawa M;Anh NT;Watanabe K;Ai NT;Tho le H;Kilgore P;Yoshino H;Toizumi M;Yasunami M;Moriuchi H;Anh DD;Ariyoshi K;Kenjiro Takazawa
混合图中的匹配森林问题是无向图中匹配问题和有向图中分支问题的一个普遍推广。Giles提出了一种寻找最大权匹配森林的算法，其中顶点数为，边数为，并给出了描述匹配森林多面体的线性系统。后来，Schrijver证明了线性系统的完全对偶积分性。本文揭示了匹配森林的另一个性质：任意混合图中匹配森林的度序列构成一个delta-拟阵，加权匹配森林导出一个赋值delta-拟阵。我们注意到，δ-拟阵不一定是均匀的，加权匹配森林诱导的赋值δ-拟阵稍微推广了著名的Dress和Wenzel的赋值δ-拟阵的概念。通过对delta-拟阵结构的研究和Giles算法的回顾，我们设计了一个更简单的加权匹配森林算法。通过将Gabow的加权匹配方法引入Giles的算法中，我们还提出了一种实时运行的加权匹配森林问题的快速算法，该算法的复杂度比以前的最佳算法有所提高。
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-time algorithm for finding a maximum-weight matching forest, whereis the number of vertices andis 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-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-time, which improves upon the previous best complexity of.