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 (10)

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

This page was built for publication: The NP-completeness column: An ongoing guide