Abstract
We first present a fixed-parameter algorithm for the NP-hard problem of deciding if there are two matchings M1 and M2 in a given graph G such that |M1| + |M2| is no less than a given number k. The algorithm runs in \(O\left(m + k\cdot k!\cdot \left(2\sqrt{2}\right)^k\cdot n^2\log n \ \right)\) time, where n (respectively, m) is the number of vertices (respectively, edges) in G. We then present a combinatorial approximation algorithm for the NP-hard problem of finding two disjoint matchings in a given edge-weighted graph G so that their total weight is maximized. The algorithm achieves an approximation ratio of roughly 0.76 and runs in \(O\left(m + n^3\alpha(n)\right)\) time, where α is the inverse Ackermann function.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Chen, Z.-Z., Konno, S., Matsushita, Y.: Approximating Maximum Edge 2-Coloring in Simple Graphs. Discrete Applied Mathematics 158, 1894–1901 (2010); A preliminary version appeared in Chen, B. (ed.) AAIM 2010. LNCS, vol. 6124, pp. 78–89. Springer, Heidelberg (2010)
Chen, Z.-Z., Tanahashi, R.: Approximating Maximum Edge 2-Coloring in Simple Graphs via Local Improvement. AAIM 2008 410, 4543–4553 (2009); A preliminary version appeared in Fleischer, R., Xu, J. (eds.) AAIM 2008. LNCS, vol. 5034, pp. 84–96. Springer, Heidelberg (2008)
Chen, Z.-Z., Tanahashi, R., Wang, L.: An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs. Journal of Discrete Algorithms 6, 205–215 (2008); A preliminary version appeared in Kao, M.-Y., Li, X.-Y. (eds.) AAIM 2007. LNCS, vol. 4508, pp. 27–36. Springer, Heidelberg (2007)
Chen, Z.-Z., Wang, L.: An Improved Randomized Approximation Algorithm for Max TSP. Journal of Combinatorial Optimization 9, 401–432 (2005)
Feige, U., Ofek, E., Wieder, U.: Approximating Maximum Edge Coloring in Multigraphs. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 108–121. Springer, Heidelberg (2002)
Gabow, H.: Implementation of Algorithms for Maximum Matching on Nonbipartite Graphs. Ph.D. Thesis, Department of Computer Science, Stanford University, Stanford, California (1973)
Gabow, H.: An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC 1983), pp. 448–456. ACM (1983)
Hartvigsen, D.: Extensions of Matching Theory. Ph.D. Thesis, Carnegie-Mellon University (1984)
Hassin, R., Rubinstein, S.: Better Approximation for Max TSP. Information Processing Letters 75, 181–186 (2000)
Hochbaum, D.: Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston (1997)
Kosowski, A.: Approximating the Maximum 2- and 3-Edge-Colorable Subgraph Problems. Discrete Applied Mathematics 157, 3593–3600 (2009)
Kosowski, A., Malafiejski, M., Zylinski, P.: Packing [1,Δ]-Factors in Graphs of Small Degree. Journal of Combinatorial Optimization 14, 63–86 (2007)
Rizzi, R.: Approximating the Maximum 3-Edge-Colorable Subgraph Problem. Discrete Mathematics 309, 4166–4170 (2009)
Serdyukov, A.I.: An Algorithm with an Estimate for the Traveling Salesman Problem of Maximum. Upravlyaemye Sistemy 25, 80–86 (1984) (in Russian)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Chen, ZZ., Fan, Y., Wang, L. (2013). Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings. In: Widmayer, P., Xu, Y., Zhu, B. (eds) Combinatorial Optimization and Applications. COCOA 2013. Lecture Notes in Computer Science, vol 8287. Springer, Cham. https://doi.org/10.1007/978-3-319-03780-6_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-03780-6_1
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03779-0
Online ISBN: 978-3-319-03780-6
eBook Packages: Computer ScienceComputer Science (R0)