×
Stockmeyer, Larry J.; Vazirani, Vijay V.

NP-completeness of some generalizations of the maximum matching problem. (English) Zbl 0493.68039

Inf. Process. Lett. 15, 14-19 (1982).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0493.68039

Cited in 1 Review
Cited in 104 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science

Keywords:

computational complexity; NP-completeness; communication network testing
Cite Review PDF
Full Text: DOI

References:

[1] Even, S.; Goldreich, O.; Tong, P., On the NP-completeness of certain network-testing problems, (Tech. Rept. #230 (1981), Dept. of Computer Science: Dept. of Computer Science Technion, Haifa, Israel) · Zbl 0532.94017
[2] Garey, M. R.; Johnson, D. S., Computers and Intractability, (A Guide to the Theory of NP-completeness (1979), Freeman: Freeman San Francisco) · Zbl 0369.90053
[3] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. J., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237-267 (1976) · Zbl 0338.05120
[4] Micali, S.; Vazirani, V. V., An \(O(|V|12.|E|)\) algorithm for finding maximum matching in general graphs, Proc. 21st Ann. IEEE Symp. on Foundations of Computer Science, 17-27 (1980)
[5] Schaefer, T. J., The complexity of satisfiability problems, Proc. 10th Ann. ACM Symp. on Theory of Computing, 216-226 (1978) · Zbl 1282.68143
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.