On Special Maximum Matchings Constructing
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
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
