Packing Non-zero A-paths via Matroid Matching
Packing Non-zero A-paths via Matroid Matching
复制标题
通过 Matroid 匹配打包非零 A 路径
DOI：
10.1016/j.dam.2016.06.001
复制
发表时间：
2016
影响因子：
1.1
通讯作者：
Yutaro Yamaguchi
中科院分区：
文献类型：
--
作者：
Shin-ichi Tanigawa;Yutaro Yamaguchi
有向图G是一个有向图，其中每个边都通过标号函数E（G）→ Γ与群Γ中的一个元素相关联。对于顶点子集A ∈ V（G），如果一条路（在底层无向图中）的起始顶点和结束顶点都属于A，并且它们之间不与A相交，则称之为A-路;如果一条A-路上沿着标号的有序积不等于Γ的单位元，则称之为非零路。Chudnovsky等人（2006）引入了非零A-路的填充问题，并给出了一个极小极大公式来刻画顶点不相交的非零A-路的最大个数。本文证明了非零A-路的填充问题可以归结为某个组合拟阵上的拟阵匹配问题，并讨论了如何基于Lovász将马德尔的S-路问题归结为拟阵匹配的思想导出极小极大公式。
A Γ-labeled graph is a directed graph G in which each edge is associated with an element of a group Γ by a label function ψ: E (G)→ Γ. For a vertex subset A⊆ V (G), a path (in the underlying undirected graph) is called an A-path if its start and end vertices belong to A and does not intersect A in between, and an A-path is called non-zero if the ordered product of the labels along the path is not equal to the identity of Γ. Chudnovsky et al.(2006) introduced the problem of packing non-zero A-paths and gave a min–max formula for characterizing the maximum number of vertex-disjoint non-zero A-paths. In this paper, we show that the problem of packing non-zero A-paths can be reduced to the matroid matching problem on a certain combinatorial matroid, and discuss how to derive the min–max formula based on Lovász’idea of reducing Mader’s S-paths problem to matroid matching.