Back
 OJDM  Vol.6 No.1 , January 2016
Solving the Maximum Matching Problem on Bipartite Star123-Free Graphs in Linear Time
Abstract: The bipartite Star123-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 Star123-free graphs a linear time algorithm of J. L. Fouquet, V. Giakoumakis and J. M. Vanherpe for finding a maximum matching in bipartite Star123, P7-free graphs presented in [2]. Our algorithm is a solution of Lozin’s conjecture.
Cite this paper: Quaddoura, R. (2016) Solving the Maximum Matching Problem on Bipartite Star123-Free Graphs in Linear Time. Open Journal of Discrete Mathematics, 6, 13-24. doi: 10.4236/ojdm.2016.61003.
References

[1]   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

[2]   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

[3]   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

[4]   Buss, S.R. and Yianilos, P.N. (1995) A Bipartite Matching Approach to Approximate String Comparison an Search. Technical Report, NEC Research Institute, Princeton.

[5]   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

[6]   Toussaint, G.T. (2004) A Comparison of Rhythmic Similarity Measures. 5th International Conference on Music Information Retrieval, 242-245.

[7]   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

[8]   Micali and Vazirani, V.V. (1980) An O(mn) Algorithm for Finding Maximum Matching in General Graphs. FOCS, 17-27.

[9]   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.

[10]   Alt, H., Blum, N., Mehlhborn, K. and Paul, M. (1991) Computing a Maximum Cardinality Matching in Bipartite Graphs in Time O(n1.5m log n) . Information Processing Letters, 37, 237-240.
http://dx.doi.org/10.1016/0020-0190(91)90195-N

[11]   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

[12]   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

[13]   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.

[14]   Quaddoura, R. (2006) Linear Time Recognition Algorithm of Bipartite Star123-Free Graphs. International Arab Journal of Information Technolog, 3, 193-202.

[15]   Bondy, J.A. and Murty, U.S.R. (1979) Graph Theory with Applications. North Holland, New York.

[16]   Berge, C. (1957) Two Theorems in Graph Theory. Proceedings of the National Academy of Sciences of the United States of America, 43, 842-844.
http://dx.doi.org/10.1073/pnas.43.9.842

 
 
Top