The NP-completeness column: an ongoing guide

Akiyama, 1980, NP-completeness of the Hamiltonian cycle problem for bipartite graphs, J. Information Processing, 3, 73 Arnborg, 1984, Complexity of finding embeddings in a k-tree Arnborg, 1984, Linear time algorithms for NP-hard problems on graphs embedded in k-trees Asano, 1983, A linear time algorithm for the subgraph homeomorphism problem for the fixed graph K3,3 Asano, 1984, A polynomial algorithm for the max-cut problem on graphs without sub-graphs homeomorphic to K3,3 Baker, 1983, Approximation algorithms for NP-complete problems on planar graphs (Preliminary Version), 265 Barahona, 1980, On the complexity of max cut Barahona, 1983 Berge, 1970 Berman, 1985 Bertossi, 1981, The edge Hamiltonian path problem is NP-complete, Inform. Process. Lett., 13, 157, 10.1016/0020-0190(81)90048-X Bertossi, 1983, Finding Hamiltonian circuits in proper interval graphs, Inform. Process. Lett., 17, 97, 10.1016/0020-0190(83)90078-9 Bonuccelli, 1980, Dominating sets and domatic number of circular arc graphs Booth, 1980, Dominating sets in chordal graphs Booth, 1979, Problems polynomially equivalent to graph isomorphism Booth, 1982, Dominating sets in chordal graphs, SIAM J. Comput., 11, 191, 10.1137/0211015 Booth, 1976, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13, 335, 10.1016/S0022-0000(76)80045-1 Brandstädt, 1986, On the restriction of some NP-complete problems to permutation graphs Chang, 1984, The k-domination and k-stability problems on sunfree chordal graphs, SIAM J. Algebraic and Discrete Methods, 5, 332, 10.1137/0605034 Chang, 1985, Covering, packing and generalized perfection, SIAM J. Algebraic and Discrete Methods, 6, 109, 10.1137/0606012 Colbourn, 1981, On testing isomorphism of permutation graphs, Networks, 11, 13, 10.1002/net.3230110103 Colbourn, 1985, Dominating cycles in series-parallel graphs, Ars Combinatorica, 19A, 107 Colbourn, 1985 Coppersmith, 1985, Solving NP-hard problems in ‘almost trees’: vertex cover, Disc. Applied Math., 10, 27, 10.1016/0166-218X(85)90057-5 Corneil, 1981, Complement reducible graphs, Disc. Applied Math., 3, 163, 10.1016/0166-218X(81)90013-5 Corneil, 1984, Clustering and domination in perfect graphs, Disc. Applied Math., 9, 27, 10.1016/0166-218X(84)90088-X Cornuejols, 1983, Halin graphs and the travelling salesman problem, Math. Programming, 26, 287, 10.1007/BF02591867 Dewdney, 1983, Fast Turing reductions between problems in NP, Chapter 4: Reductions between NP-complete problems Farber, 1982, Application of L.P. duality to problems involving independence and domination Farber, 1982, Independent domination in chordal graphs, Operations Res. Lett., 1, 134, 10.1016/0167-6377(82)90015-3 Farber, 1983, Characterizations of strongly chordal graphs, Discrete Math., 43, 173, 10.1016/0012-365X(83)90154-1 Farber, 1984, Domination, independent domination, and duality in strongly chordal graphs, Disc. Applied Math., 7, 115, 10.1016/0166-218X(84)90061-1 M. Farber and J. M. Keil, Domination in permutation graphs, J. Algorithms, to appear. Filotti, 1979, On determining the genus of a graph in O(VO(g)) steps, 27 Garey, 1977, The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math., 32, 826, 10.1137/0132071 Garey, 1980, The complexity of coloring circular arcs and chords, SIAM J. Algebraic and Discrete Methods, 1, 216, 10.1137/0601025 Gavril, 1974, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combinatorial Theory Ser. B, 16, 47, 10.1016/0095-8956(74)90094-X Gavril, 1975, A recognition algorithm for the intersection graphs of directed paths in directed trees, Discrete Math., 13, 237, 10.1016/0012-365X(75)90021-7 Gavril, 1978, A recognition algorithm for the intersection graphs of paths in trees, Discrete Math., 23, 211, 10.1016/0012-365X(78)90003-1 Golumbic, 1980 M. C. Golumbic and R. E. Jamison, The edge intersection graphs of paths in a tree, J. Combinatorial Theory Ser. B, to appear. Grötschel, 1981, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169, 10.1007/BF02579273 Grötschel, 1981 Gupta, 1982, Efficient algorithms for interval graphs and circular-arc graphs, Networks, 12, 459, 10.1002/net.3230120410 Gurari, 1984, Improved dynamic programming algorithms for bandwidth minimization and the mincut linear arrangement problem, J. Algorithms, 5, 531, 10.1016/0196-6774(84)90006-3 Gurevich, 1984, Solving NP-hard problems on graphs that are almost trees and an application to facility location problems, J. Assoc. Comput. Mach., 31, 459, 10.1145/828.322439 Harary, 1969 Hedetniemi, 1983, A linear algorithm for the domination number of a cactus Holyer, 1983, The NP-completeness of edge coloring, SIAM J. Comput., 10, 718, 10.1137/0210055 Hsu, 1985, Maximum weight clique algorithms for circular-arc graphs and circle graphs, SIAM J. Comput., 14, 224, 10.1137/0214018 Itai, 1982, Hamilton paths in grid graphs, SIAM J. Comput., 11, 676, 10.1137/0211056 Kasteleyn, 1967, Graph theory and crystal physics, 44 Keil, 1985 Kikuno, 1983, A linear algorithm for the domination number of a series-parallel graph, Disc. Applied Math., 5, 299, 10.1016/0166-218X(83)90003-3 F. T. Leighton, private communication (1985). Lovász, 1983, Perfect graphs, 55 Lueker, 1979, A linear time algorithm for deciding interval graph isomorphism, J. Assoc. Comput. Mach., 26, 183, 10.1145/322123.322125 Luks, 1980, Isomorphism of bounded valence can be tested in polynomial time, J. Comput. System Sci., 25, 42, 10.1016/0022-0000(82)90009-5 Manacher, 1984 Mansfield, 1982, Determining the thickness of graphs is NP-hard, 93, 9 Miller, 1980, Isomorphism testing for graphs of bounded genus, 225 Miller, 1983, Isomorphism of k-contractible graphs: A generalization of bounded valence and bounded genus, Information and Control, 56, 1, 10.1016/S0019-9958(83)80047-3 Minty, 1980, On maximal independent sets of vertices in claw-free graphs, J. Combinatorial Theory Ser. B, 28, 284, 10.1016/0095-8956(80)90074-X Monien, 1981, Bandwidth-constrained NP-complete problems, 207 Monma, 1985 Orlin, 1981, An O(n2) algorithm for coloring proper circular arc graphs, SIAM J. Algebraic and Discrete Methods, 2, 88, 10.1137/0602012 Proskurowski, 1982, Efficient vertex- and edge-coloring of outerplanar graphs Saxe, 1980, Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time, SIAM J. Algebraic and Discrete Methods, 1, 363, 10.1137/0601042 Sbihi, 1980, Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile, Discrete Math., 29, 53, 10.1016/0012-365X(90)90287-R A. Schäffer, private communication (1985). Supowit, 1985, Recognizing circle graphs in polynomial time Syslo, 1982, The subgraph isomorphism problem for outerplanar graphs, Theor. Comput. Sci., 17, 91, 10.1016/0304-3975(82)90133-5 Syslo, 1982, The induced subgraph isomorphism problem for series-parallel graphs is NP-complete Syslo, 1983, NP-complete problems on some tree-structured graphs: a review, 342 Takamizawa, 1982, Linear-time computability of combinatorial problems on series-parallel graphs, J. Assoc. Comput. Mach., 29, 623, 10.1145/322326.322328 Tarjan, 1984, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 566, 10.1137/0213035 Tucker, 1971, Matrix characterization of circular-arc graphs, Pacific J. Math., 39, 535, 10.2140/pjm.1971.39.535 Tucker, 1971, Matrix characterization of circular-arc graphs, SIAM J. Comput., 9, 1, 10.1137/0209001 Tucker, 1980, An efficient test for circular-arc graphs, SIAM J. Comput., 9, 1, 10.1137/0209001 Valdes, 1982, The recognition of series parallel digraphs, SIAM J. Comput., 11, 298, 10.1137/0211023 Valiant, 1979, The complexity of computing the permanent, Theor. Comput. Sci., 8, 189, 10.1016/0304-3975(79)90044-6 Wald, 1982, Steiner trees in outerplanar graphs Wald, 1983, Steiner trees, partial 2-trees, and minimum IFI networks, Networks, 13, 159, 10.1002/net.3230130202 White, 1985, Steiner trees, connected domination and strongly chordal graphs, Networks, 15, 109, 10.1002/net.3230150109