Maximum Weighted Matching with Few Edge Crossings for 2-Layered Bipartite Graph
| Autor: | Haraguchi, Kazuya, Torii, Kotaro, Endo, Motomu |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 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) for c=1 and O(k^3+k^2n+m(m+log n)) for c=2, respectively, where n=|V|, m=|E| and k=|X|. Comment: 18 pages, 5 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|