Matching and P2-Packing: Weighted Versions Conference Paper uri icon

abstract

  • Parameterized algorithms are presented for the weighted P 2-Packing problem, which is a generalization of the famous Graph Matching problem. The algorithms are based on the following new techniques and observations: (1) new study on structure relationship between graph matchings in general graphs and P2-packings in bipartite graphs; (2) an effective graph bi-partitioning algorithm; and (3) a polynomial-time algorithm for a constrained weighted P2-Packing problem in bipartite graphs. These techniques lead to randomized and deterministic parameterized algorithms that significantly improve the previous best upper bounds for the problem for both weighted and unweighted versions. 2011 Springer-Verlag.

name of conference

  • Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Feng, Q., Wang, J., & Chen, J.

citation count

  • 5

complete list of authors

  • Feng, Qilong||Wang, Jianxin||Chen, Jianer

publication date

  • August 2011