The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(82)90026-8zbMath0494.68050OpenAlexW4253517210MaRDI QIDQ5905225

David S. Johnson

Publication date: 1982

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(82)90026-8

zbMATH Keywords

NP-complete problemsNP-completenesschromatic indexgraph isomorphismtotal unimodularitygraph genussubgraph homeomorphismcomposite numberimperfect graph3-processor schedulingminimum-length triangulationspanning tree parity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem books (00A07)

Related Items

Hamiltonian circuits in interval graph generalizations, An approximation scheme for strip packing of rectangles with bounded dimensions, Formally proving size optimality of sorting networks, HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting, Incremental bipartite drawing problem, Heuristics and meta-heuristics for 2-layer straight line crossing minimization, A catalog of minimally nonideal matrices, A useful transform of standard input data for a classical NP-complete problem, Quadratic forms and the graph isomorphism problem, A tabu search algorithm for the bipartite drawing problem