`` Strong NP-Completeness Results

DOI10.1145/322077.322090zbMath0379.68035OpenAlexW2009990213WikidataQ55899907 ScholiaQ55899907MaRDI QIDQ4158479

Michael R. Garey, David S. Johnson

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

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items (only showing first 100 items - show all)

The complexity of the 0/1 multi-knapsack problem ⋮ An asymptotically exact polynomial algorithm for equipartition problems ⋮ Minimal triangulations of graphs: a survey ⋮ A compact labelling scheme for series-parallel graphs ⋮ Unimodular functions ⋮ The two-machine sequence dependent flowshop scheduling problem ⋮ Computation on binary tree-networks ⋮ The principle of optimality in the design of efficient algorithms ⋮ An approximation algorithm for maximum packing of 3-edge paths ⋮ A note on scheduling multiprocessor tasks with precedence constraints on parallel processors ⋮ Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem ⋮ Edge-connectivity augmentation problems ⋮ NP-completeness of the linear complementarity problem ⋮ A note on complete problems for complexity classes ⋮ Practical solutions for a dock assignment problem with trailer transportation ⋮ Approximation of the parallel machine scheduling problem with additional unit resources ⋮ Optimal broadcast domination in polynomial time ⋮ The maximum k-colorable subgraph problem for chordal graphs ⋮ Sink location to find optimal shelters in evacuation planning ⋮ Approximation schemes for Euclidean vehicle routing problems with time windows ⋮ The \(p\)-median problem: a survey of metaheuristic approaches ⋮ Single machine scheduling problems with resource dependent release times ⋮ Algorithms to solve the orienteering problem: A comparison ⋮ Deleting completed transactions ⋮ Tighter bounds of the First Fit algorithm for the bin-packing problem ⋮ `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders ⋮ Computational complexity and approximation for a generalization of the Euclidean problem on the Chebyshev center ⋮ Lot-sizing scheduling with batch setup times ⋮ On the Boolean connectivity problem for Horn relations ⋮ Multi-criteria scheduling: an agent-based approach for expert knowledge integration ⋮ Cop-robber guarding game with cycle robber-region ⋮ The node-deletion problem for hereditary properties is NP-complete ⋮ Complexity results for scheduling chains on a single machine ⋮ Toward a unified approach for the classification of NP-complete optimization problems ⋮ Approximation schemes for generalized two-dimensional vector packing with application to data placement ⋮ Online scheduling with rearrangement on two related machines ⋮ Parallel machines scheduling with machine maintenance for minsum criteria ⋮ Non deterministic polynomial optimization problems and their approximations ⋮ Scheduling jobs with equal processing times subject to machine eligibility constraints ⋮ Scheduling on same-speed processors with at most one downtime on each machine ⋮ On minimal augmentation of a graph to obtain an interval graph ⋮ A probabilistic analysis of the multiknapsack value function ⋮ General approximation algorithms for some arithmetical combinatorial problems ⋮ A note on the complexity of \(L _{p }\) minimization ⋮ Scheduling batches on parallel machines with major and minor set-ups ⋮ Online scheduling with one rearrangement at the end: revisited ⋮ Analysis of relaxations for the multi-item capacitated lot-sizing problem ⋮ Guard games on graphs: keep the intruder out! ⋮ Optimal algorithms for online scheduling with bounded rearrangement at the end ⋮ The complexity of equality constraint languages ⋮ Chordal graphs and upper irredundance, upper domination and independence ⋮ The hierarchical network design problem with transshipment facilities ⋮ Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems ⋮ COSINE: A new graph coloring algorithm ⋮ Finding large holes ⋮ Constructive complexity ⋮ A faster algorithm for the resource allocation problem with convex cost functions ⋮ Approximate solution of NP optimization problems ⋮ Knapsack problems for NL ⋮ Complexity of fixed-size bit-vector logics ⋮ Location and sizing of offshore platforms for oil exploration ⋮ Limitations of incremental dynamic programming ⋮ Scheduling multiprocessor tasks on three dedicated processors ⋮ A logic for programming with complex objects ⋮ An efficient algorithm for finding a maximum weight 2-independent set on interval graphs ⋮ On reversal-bounded picture languages ⋮ Maximizing business value by optimal assignment of jobs to resources in grid computing ⋮ Approximating the tree and tour covers of a graph ⋮ The max clique problem in classes of string-graphs ⋮ Structure of polynomial-time approximation ⋮ A linear kernel for a planar connected dominating set ⋮ Minimal split completions ⋮ Finding the longest isometric cycle in a graph ⋮ A minimum 3-connectivity augmentation of a graph ⋮ Theoretical investigations on maximal dual feasible functions ⋮ A greedy approximation for minimum connected dominating sets ⋮ On the complexity of decidable cases of the commutation problem of languages ⋮ Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint ⋮ On the complexity of crossings in permutations ⋮ Optimal and heuristic solution methods for a multiprocessor machine scheduling problem ⋮ Approximation algorithms for scheduling unrelated parallel machines ⋮ Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem ⋮ Computational complexity of norm-maximization ⋮ An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs ⋮ An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm ⋮ A heuristic algorithm for the mini-max spanning forest problem ⋮ A branch-and-bound algorithm for the mini-max spanning forest problem ⋮ Bounding prefix transposition distance for strings and permutations ⋮ How hard is it to find extreme Nash equilibria in network congestion games? ⋮ PTAS for connected vertex cover in unit disk graphs ⋮ Minimum directed 1-subtree relaxation for score orienteering problem ⋮ The largest tree in a random graph ⋮ Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses ⋮ On legal path problems in digraphs ⋮ Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete ⋮ On the computational complexity of path cover problems ⋮ Fuzzy shortest paths ⋮ Planar graph coloring is not self-reducible, assuming P\(\neq NP\) ⋮ Cellular automata and discrete neural networks ⋮ A bound for the Dilworth number

This page was built for publication: `` Strong NP-Completeness Results