On Special Maximum Matchings Constructing

Authors

  • Rafayel R. Kamalian Institute for Informatics and Automation Problems of NAS RA;Yerevan State University
  • Vahan V. Mkrtchyan Institute for Informatics and Automation Problems of NAS RA;Yerevan State University

Abstract

For bipartite graphs the NP-completeness is proved for the problem of existence of maximum matching which removal leads to a graph with given lower(upper) bound for the cardinality of its maximum matching.

References

Harary F.,Graph Theory" ,Addison-Wesley, Reading, MA,1969.

Papadimitriou C.H.,Steiglitz K.,Combinatorial optimization: Algorithms and Complexity, PREN TICE-H ALL, IN C Englewood Cliffs,New Jersey,1982.

Cook S.A.,The complexity of theorem-proving procedures, Proc. 3rd Ann. ACM Symp. On Theory of Computing, Association for Computing Machinery, New York,1971 , pp.151-158.

Karp R. M.,Reducibility among combinatorial problems, in R.E.Miller and J.W.Thatchers(eds) , Complexity of Computer Computations, Plenum Press, New York,1972, pp.85-103.

Garey M.R. , Johnson D .S., Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco: W. H . Freeman & Company, Publishers, 1979.

Garey M.R.,Johnson D.S. and Stockmeyer L.Some simplified N P-complete graph problems",Theor. Comput. Sci 1 ,No.3,237-267,1976.

Even S., Kariv O.An O( n 2:5 ) Algorithm for Maximum Matching in General Graphs, Proc. Sixteenth Annual Symp. On Foundations of Computer Science, Berkeley, California: IEEE(1975),100-112.

Downloads

Published

2021-12-10

How to Cite

Kamalian, R. R. ., & Mkrtchyan, V. V. . (2021). On Special Maximum Matchings Constructing. Mathematical Problems of Computer Science, 24, 62–75. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/571