Research ArticleOpen AccessGoogle Scholar indexed
Solving the Maximum Matching Problem on Bipartite <i>Star</i><sub>123</sub>-Free Graphs in Linear Time
Department of Computer Science, Faculty of Information Technology, Zarqa University, Zarqa, Jordan
- 1 Department of Computer Science, Faculty of Information Technology, Zarqa University, Zarqa, Jordan
Open Journal of Discrete Mathematics·Volume 06 (2015)·Pages 13–24·Published 17 December 2015·DOI10.4236/ojdm.2016.61003
Copy link · social · email
Abstract
The bipartite Star 123 -free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star 123 -free graphs a linear time algorithm of J. L. Fouquet, V. Giakoumakis and J. M. Vanherpe for finding a maximum matching in bipartite Star 123 , P 7 -free graphs presented in [2]. Our algorithm is a solution of Lozin’s conjecture.
KeywordsBipartite GraphsDecomposition of GraphsDesign and Analysis of AlgorithmsMatching
- Lozin, V.V. (2002) Bipartite Graphs without a Skew Star. Discrete Mathematics, 257, 83-100. http://dx.doi.org/10.1016/S0012-365X(01)00471-X
- Fouquet, J.L., Giakoumakis, V. and Vanherpe, J.M. (1999) Bipartite Graphs Totally Decomposable by Canonical Decomposition. International Journal of Foundation of Computer Science, 10, 513-533. http://dx.doi.org/10.1142/S0129054199000368
- Ben-Dor, A., Karp, R.M., Schwikowski, B. and Shamir, R. (2003) The Restriction Scaf-Fold Problem. Journal of Computational Biology, 10, 385-398. http://dx.doi.org/10.1089/10665270360688084
- Buss, S.R. and Yianilos, P.N. (1995) A Bipartite Matching Approach to Approximate String Comparison an Search. Technical Report, NEC Research Institute, Princeton.
- Demirci, M.F., Shokoufandeh, A., Keselman, Y., Bretzner, L. and Dickinson, S. (2006) Object Recognition as Many-to-Many Feature Matching. International Journal of Computer Vision, 69, 203-222. http://dx.doi.org/10.1007/s11263-006-6993-y
- Toussaint, G.T. (2004) A Comparison of Rhythmic Similarity Measures. 5th International Conference on Music Information Retrieval, 242-245.
- Toussaint, G.T. (2005) The Geometry of Musical Rhythm. Japan Conference on Discrete and Computational Geometry, Berlin-Heidelberg, 198-212. http://dx.doi.org/10.1007/11589440_20
- Micali and Vazirani, V.V. (1980) An O( m √ n ) Algorithm for Finding Maximum Matching in General Graphs. FOCS, 17-27.
- Moitra and Johnson, R.C. (1989) A Parallel Algorithm for Maximum Matching in Interval Graphs. Proceedings of International Conference on Parallel Processing, 3, 114-120.
- Alt, H., Blum, N., Mehlhborn, K. and Paul, M. (1991) Computing a Maximum Cardinality Matching in Bipartite Graphs in Time O( n 1.5 √ m log n ) . Information Processing Letters, 37, 237-240. http://dx.doi.org/10.1016/0020-0190(91)90195-N
- Yu, M.S. and Yang, C.H. (1993) An O(n) Time Algorithm for Maximum Matching on Cographs. Information Processing Letters, 47, 89-93. http://dx.doi.org/10.1016/0020-0190(93)90230-7
- Fouquet, J.L., Parfenoff, I. and Thuillier, H. (1997) An O(n) Time Algorithm for Maximum Matching in P4-Tidy Graphs. Information Processing Letters, 62, 281-287. http://dx.doi.org/10.1016/S0020-0190(97)00081-1
- Quaddoura, R. (2014) An O(n) Time Algorithm for Maximum Induced Matching In Bipartite Star123-Free Graphs. World of Computer Science and Information Technology Journal (WCSIT), 4, 38-41.