On bipartite matchings of minimum density |
| |
| Authors: | Mikhail J Atallah Susanne E Hambrusch |
| |
| Institution: | 1. Department of Computer Science, University of Oxford, United Kingdom;2. Department of Computer Science, Ariel University, Israel;3. School of Computing, National University of Singapore, Singapore;1. University of Oxford, UK;2. Alan Turing Institute, UK;3. AGH University, Poland;4. University of Tokyo, Japan;5. Google Research, Thailand;6. Technische Universität Berlin, Germany;7. National University of Singapore, Singapore |
| |
| Abstract: | We study the complexity of bipartite matchings between points on two horizontal lines when the density (i.e., the number of edges of the matching that cross any vertical cut) is to be minimized. We show that finding density-minimizing matchings is considerably harder than finding weight-minimizing matchings by proving that the problem is NP-hard for general bipartite graphs. For a number of variants we present a new combinatorial characterization of the optimal density that leads to efficient and elegant algorithms. The problem of finding a matching of minimum density has applications in the area of circuit layout. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
