The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(81)90037-7zbMath0494.68047OpenAlexW4250585487MaRDI QIDQ5905222

David S. Johnson

Publication date: 1981

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

Full work available at URL: https://doi.org/10.1016/0196-6774(81)90037-7

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) Linear programming (90C05) Problem books (00A07) Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05)

Related Items (22)

The graph sandwich problem for 1-join composition is NP-complete ⋮ Complexity analysis of job-shop scheduling with deteriorating jobs ⋮ Complexity and approximability of scheduling resumable proportionally deteriorating jobs ⋮ SINGLE-MACHINE SCHEDULING WITH PROPORTIONALLY DETERIORATING JOBS SUBJECT TO AVAILABILITY CONSTRAINTS ⋮ Scheduling deteriorating jobs subject to job or machine availability constraints ⋮ A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum ⋮ Scheduling resumable deteriorating jobs on a single machine with non-availability constraints ⋮ A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints ⋮ A concise survey of scheduling with time-dependent processing times ⋮ Scheduling a variable maintenance and linear deteriorating jobs on a single machine ⋮ An appraisal of computational complexity for operations researchers ⋮ Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration ⋮ Scheduling time-dependent jobs under mixed deterioration ⋮ Preemptive scheduling with simple linear deterioration on a single machine ⋮ ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation ⋮ A review of four decades of time-dependent scheduling: main results, new topics, and open problems ⋮ Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan ⋮ NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times ⋮ Certain NP-complete matching problems ⋮ An approach to the subgraph homeomorphism problem ⋮ Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey ⋮ Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs

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