Nonbipartite Dulmage-Mendelsohn Decomposition for Berge Duality
Nonbipartite Dulmage-Mendelsohn Decomposition for Berge Duality
复制标题
Berge 对偶性的非二部 Dulmage-Mendelsohn 分解
DOI：
10.1007/978-3-319-94776-1_25
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Nanao Kita
中科院分区：
文献类型：
--
作者：
Miguel Cardona;Lukas Klausner;Diego A. Mejia;足立真訓;Nanao Kita
Dulmage-Mendelsohn分解是匹配理论中适用于二部图的经典正则分解，不仅在矩阵计算领域有广泛的应用，而且在拟阵优化理论中提供了一个原型结构。Dulmage-Mendelsohn分解是用二分图的两种颜色类来描述和证明的，因此将这种分解推广到非二分图是一项困难的任务。在本文中，我们得到了一个新的典型分解，这是一个推广的Dulmage-Mendelsohn分解的任意图使用最近推出的匹配理论的工具，thebasilica分解。我们的结果使我们能够以统一的方式理解所有已知的正则分解。此外，我们应用这个结果导出了一个新的关于障碍的定理。最大匹配问题的对偶定理是CelebratedBerge公式，其中对偶优化器被称为障碍。关于最大障碍的几个结果已经由已知的典型分解导出;然而，对于一般的图，还没有已知的特征。本文给出了一般图的极大障碍族的一个刻划，发展和统一了已有的结果。
TheDulmage-Mendelsohn decompositionis a classicalcanonical decompositionin matching theory applicable for bipartite graphs and is famous not only for its application in the field of matrix computation, but also for providing a prototypal structure in matroidal optimization theory. The Dulmage-Mendelsohn decomposition is stated and proved using the two color classes of a bipartite graph, and therefore generalizing this decomposition for nonbipartite graphs has been a difficult task. In this paper, we obtain a new canonical decomposition that is a generalization of the Dulmage-Mendelsohn decomposition for arbitrary graphs using a recently introduced tool in matching theory, thebasilica decomposition. Our result enables us to understand all known canonical decompositions in a unified way. Furthermore, we apply our result to derive a new theorem regardingbarriers. The duality theorem for the maximum matching problem is the celebratedBerge formula, in which dual optimizers are known as barriers. Several results regarding maximal barriers have been derived by known canonical decompositions; however, no characterization has been known for general graphs. In this paper, we provide a characterization of the family ofmaximal barriersin general graphs, in which the known results are developed and unified.
登录
查看更多内容
揭示障碍：基于 Lovász 公式的规范划分的推广
DOI：
10.1007/978-3-319-03780-6_35
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Nanao Kita
通讯作者：
Nanao Kita
完美匹配一般图的偏序结构和规范划分的推广
DOI：
10.1007/978-3-642-35261-4_12
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Nanao Kita
通讯作者：
Nanao Kita
DOI：
10.4153/cjm-1958-052-0
发表时间：
1958
期刊：
Canadian Journal of Mathematics
影响因子：
--
作者：
A. Dulmage;N. S. Mendelsohn
通讯作者：
A. Dulmage;N. S. Mendelsohn
二分图的两种算法
DOI：
10.1137/0111014
发表时间：
1963
期刊：
Journal of The Society for Industrial and Applied Mathematics
影响因子：
--
作者：
A. Dulmage;N. S. Mendelsohn
通讯作者：
N. S. Mendelsohn
DOI：
--
发表时间：
1960
期刊：
--
影响因子：
--
作者：
Anton Kotzig
通讯作者：
Anton Kotzig