×

zbMATH — the first resource for mathematics

Some simplified NP-complete graph problems. (English) Zbl 0338.05120

MSC:
05C99 Graph theory
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adolphson, D.; Hu, T.C., Optimal linear ordering, SIAM J. appl. math., 25, 403-423, (1973) · Zbl 0274.90061
[2] Brooks, R.L., On coloring the nodes of a network, Proc. Cambridge philos. soc., 37, 194-197, (1941) · Zbl 0027.26403
[3] Cook, S.A., The complexity of theorem-proving procedures, Proceedings of the 4th annual ACM symposium on theory of computing, 151-158, (1971)
[4] Edmonds, J.; Johnson, E.L., Matching: A well-solved class of integer linear programs, (), 89-92
[5] Even, S.; Lempel, A.; Pnueli, A., Permutation graphs and transitive graphs, J. ACM, 19, 400-410, (1972) · Zbl 0251.05113
[6] Garey, M.R.; Graham, R.L.; Ullman, J.D., Worst-case analysis of memory allocation algorithms, Stoc, 143-150, (1972) · Zbl 0357.68027
[7] Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. computing, 1, 180-187, (1972) · Zbl 0227.05116
[8] Gavril, F., Algorithms for a maximum clique and a maximum independent set of a circle graph, Networks, 3, 261-273, (1973) · Zbl 0259.05125
[9] Graham, R.L., Bounds on multiprocessing anomalies and related packing algorithms, Proceedings of the AFIPS spring joint computer conference, 205-217, (1972)
[10] Herrmann, P., Reducibility among combinatorial problems, ()
[11] Johnson, D.S., Fast algorithms for bin packing, J. compt. system sci., 8, 272-314, (1974) · Zbl 0284.68023
[12] Johnson, D.S., Approximation algorithms for combinatorial problems, J. compt. system sci., 9, 178-256, (1974) · Zbl 0296.65036
[13] Karp, R.M., Reducibility among combinatorial problems, (), 85-104 · Zbl 0366.68041
[14] Orlova, G.I.; Dorfman, Y.G., Finding the maximum cut in a graph, Engrg. cybernetics, 10, 502-506, (1972) · Zbl 0247.05151
[15] Sahni, S., Some related problems from network flows, game theory, and integer programming, Proceedings of 13th annual IEEE symposium on switching and automata theory, 130-138, (1972)
[16] Sahni, S., On the knapsack and other computationally related problems, ()
[17] Sethi, R., Complete register allocation problems, Proceedings of the 5th annual ACM symposium on theory of computing, 182-195, (1973) · Zbl 0308.68018
[18] Stockmeyer, L., Planar 3-colorability is polynomial complete, SIGACT news, 5, No. 3, 19-25, (1973)
[19] Ullman, J.D., Polynomial complete scheduling problems, 4th symp. on operating system principles, 96-101, (1973)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.