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.
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(m√n) 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.5√m 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
