Equitable partitions into matchings and coverings in mixed graphs
Equitable partitions into matchings and coverings in mixed graphs
复制标题
混合图中的匹配和覆盖的公平划分
DOI：
10.1016/j.disc.2021.112651
复制
发表时间：
2022
影响因子：
0.8
通讯作者：
Yu Yokoi
中科院分区：
文献类型：
--
作者：
Tamas Kiraly;Yu Yokoi
匹配和覆盖是图论中的中心话题。这两者之间的密切关系是许多基本算法和多面体结果的关键。对于混合图，匹配森林的概念是匹配和分支的一种普遍推广，本文提出了混合边覆盖的概念作为匹配森林的覆盖对应，并将匹配覆盖框架推广到混合图.虽然算法和多面体的结果扩展相当容易，分区问题是相当困难的混合情况下。我们解决的问题，分区的混合图匹配的森林或混合边缘覆盖，使所有部分都是平等的一些标准，如边缘/弧数或总尺寸。此外，我们提供了最好的多准则均衡。
Matchings and coverings are central topics in graph theory. The close relationship between these two has been key to many fundamental algorithmic and polyhedral results. For mixed graphs, the notion of matching forest was proposed as a common generalization of matchings and branchings.In this paper, we propose the notion of mixed edge cover as a covering counterpart of matching forest, and extend the matching–covering framework to mixed graphs. While algorithmic and polyhedral results extend fairly easily, partition problems are considerably more difficult in the mixed case. We address the problems of partitioning a mixed graph into matching forests or mixed edge covers, so that all parts are equal with respect to some criterion, such as edge/arc numbers or total sizes. Moreover, we provide the best possible multicriteria equalization.