The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(82)90018-9zbMath0494.68049OpenAlexW4244027514MaRDI QIDQ5905224

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)90018-9

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

Diameter partitioning, Novel hybrid heuristics for an extension of the dynamic relay deployment problem over disaster areas, A novel dynamic minimum spanning tree based clustering method for image mining, ON THE DISCRETE UNIT DISK COVER PROBLEM, Minimum Dominating Set Problem for Unit Disks Revisited, A Scheme for Computing Minimum Covers within Simple Regions, Abductive Reasoning in 2D Geospatial Problems, APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS, Polynomial time approximation schemes for minimum disk cover problems, Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances, Computing Euclidean maximum spanning trees, Pattern minimisation in cutting stock problems, Unit disk graphs, Covering Points by Unit Disks of Fixed Location, Covering a set of points in multidimensional space, Watchman routes under limited visibility, AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER, Polynomial-time approximation schemes for piercing and covering with applications in wireless networks, The within-strip discrete unit disk cover problem, Minimum-diameter covering problems, On Geometric Set Cover for Orthants, On the Discrete Unit Disk Cover Problem, THE CONTINUOUS STOP LOCATION PROBLEM IN PUBLIC TRANSPORTATION NETWORKS, Density-based O-Means clustering algorithm using minimum spanning tree, Approximating uniform triangular meshes in polygons.