Efficient Algorithms for Variants of Weighted Matching and Assignment Problems |
| |
Authors: | Satyajit Banerjee Atish Datta Chowdhury Subhas Kumar Ghosh |
| |
Institution: | (1) Honeywell Technology Solutions, 151/1, Doraisanipalya, Bannerghatta Road, Bangalore, 560076, India |
| |
Abstract: | Obtaining a matching in a graph satisfying a certain objective is an important class of graph problems. Matching algorithms
have received attention for several decades. However, while there are efficient algorithms to obtain a maximum weight matching,
not much is known about the maximum weight maximum cardinality, and maximum cardinality maximum weight matching problems for
general graphs. Our contribution in this work is to show that for bounded weight input graphs one can obtain an algorithm
for both maximum weight maximum cardinality (for real weights), and maximum cardinality maximum weight matching (for integer
weights) by modifying the input and running the existing maximum weight matching algorithm. Also, given the current state
of the art in maximum weight matching algorithms, we show that, for bounded weight input graphs, both maximum weight maximum
cardinality, and maximum cardinality maximum weight matching have algorithms of similar complexities to that of maximum weight
matching. Subsequently, we also obtain approximation algorithms for maximum weight maximum cardinality, and maximum cardinality
maximum weight matching.
|
| |
Keywords: | Mathematics Subject Classification (2000)" target="_blank">Mathematics Subject Classification (2000) Primary 68R10 68W25 Secondary 05C85 |
本文献已被 SpringerLink 等数据库收录! |
|