Maximum weighted matching with few edge crossings for 2-layered bipartite graph
Maximum weighted matching with few edge crossings for 2-layered bipartite graph
复制标题
2层二分图的最小边交叉的最大加权匹配
DOI：
10.1016/j.dam.2020.07.017
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Endo Motomu
中科院分区：
文献类型：
--
作者：
Haraguchi Kazuya;Torii Kotaro;Endo Motomu
设c为非负常数。设G=（V，E）是一个边权二部图，它有2层图和一个相交边对族X ∈ E× E.我们考虑的问题是找到一个最大的加权匹配M，使得M中的每条边最多与M中的其他c条边相交，并且M中的所有边交叉都包含在X中。在本文中，我们提出了多项式时间算法的情况下，c= 1和2。算法的时间复杂度对于c= 1分别为O（（k+ m）logn + n）或O（k+ n2），对于c= 2分别为O（k3 + k2 n+ m2 + min {mlogn，n2}），其中n=| V|，m=| E|和k=| X|.
Let c denote a non-negative constant. Suppose that we are given an edge-weighted bipartite graph G=(V, E) with its 2-layered drawing and a family X⊆ E× E of intersecting edge pairs. We consider the problem of finding a maximum weighted matching M∗ such that each edge in M∗ intersects with at most c other edges in M∗, and that all edge crossings in M∗ are contained in X. In the present paper, we propose polynomial-time algorithms for the cases of c= 1 and 2. The time complexities of the algorithms are O ((k+ m) log n+ n) or O (k+ n 2) for c= 1 and O (k 3+ k 2 n+ m 2+ min {m log n, n 2}) for c= 2, respectively, where n=| V|, m=| E| and k=| X|.