Some simplified NP-complete graph problems. (English) Zbl 0338.05120
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) · Zbl 0253.68020 |
| [4] | Edmonds, J.; Johnson, E. L., Matching: A well-solved class of integer linear programs, (Combinatorial Structures and Their Applications (1970), Gordon and Breach: Gordon and Breach New York), 89-92 · Zbl 0258.90032 |
| [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, (Masters Thesis (1973), Massachusetts Institute of Technology) |
| [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, (Millera, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 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, (Doctoral Thesis (1973), Cornell University) |
| [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. 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.
