The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(82)90011-6zbMath0494.68048OpenAlexW4255268306MaRDI QIDQ5905223

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)90011-6

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

Minimum dimension embedding of finite metric spaces, Computing crossing numbers in quadratic time, Bipartite permutation graphs, On the complexity of H-coloring, A tabu thresholding algorithm for arc crossing minimization in bipartite graphs, Drawing graphs with mathematical programming and variable neighborhood search, Colouring, constraint satisfaction, and complexity, Polynomial graph-colorings, Fixed edge-length graph drawing is NP-hard, Polynomial graph-colorings, Hereditarily hard \(H\)-colouring problems