`` Strong NP-Completeness Results

DOI10.1145/322077.322090zbMath0379.68035WikidataQ55899907 ScholiaQ55899907MaRDI QIDQ4158479

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322077.322090

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90B35: Deterministic scheduling theory in operations research

68N01: General topics in the theory of software

68W99: Algorithms in computer science

Related Items

A note on LPT scheduling, Algorithms for minclique scheduling problems, On the complexity of coupled-task scheduling, Approximate solution of NP optimization problems, Knapsack problems for NL, A logic for programming with complex objects, Approximating the tree and tour covers of a graph, Chordal graphs and upper irredundance, upper domination and independence, The hierarchical network design problem with transshipment facilities, COSINE: A new graph coloring algorithm, Finding large holes, Constructive complexity, Location and sizing of offshore platforms for oil exploration, Scheduling multiprocessor tasks on three dedicated processors, An efficient algorithm for finding a maximum weight 2-independent set on interval graphs, On reversal-bounded picture languages, The max clique problem in classes of string-graphs, A minimum 3-connectivity augmentation of a graph, Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem, An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs, A heuristic algorithm for the mini-max spanning forest problem, A branch-and-bound algorithm for the mini-max spanning forest problem, Minimum directed 1-subtree relaxation for score orienteering problem, Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete, Modeling uncertainty in networks, A note on generalizing the maximum lateness criterion for scheduling, A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective, Database placement in communication networks for minimizing the overall transmission cost, Feasibility of scheduling lot sizes of two frequencies on one machine, A convex geometric approach to counting the roots of a polynomial system, A graph partitioning heuristic for the parallel pseudo-exhaustive logical test of VLSI combinational circuits, Judicious partitions of hypergraphs, On locating cubic subgraphs in bounded-degree connected bipartite graphs, On the use of Boolean methods for the computation of the stability number, Maximizing the weighted number of on-time jobs in single machine scheduling with time windows, Single machine scheduling with discretely controllable processing times, On the two-connected planar spanning subgraph polytope, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Covering regular graphs, Is a unit-job shop not easier than identical parallel machines?, Fault tolerant \(K\)-center problems, The discrete lot-sizing and scheduling problem: Complexity and modification for batch availability, Polynomial time approximation algorithms for machine scheduling: Ten open problems, Scheduling shops to minimize the weighted number of late jobs, On component-size bounded Steiner trees, A new algorithm for the propositional satisfiability problem, Polynomially solvable cases for the maximum stable set problem, Shop scheduling problems with multiprocessor tasks on dedicated processors, A local search approach for two-dimensional irregular cutting, An optimal algorithm for preemptive on-line scheduling, Approximation for knapsack problems with multiple constraints, Using a tabu search approach for solving the two-dimensional irregular cutting problem