The NP-Completeness Column: An Ongoing Guide

No abstract is available for this paper.

• Publication year

  1982

• Venue

  J. Algorithms

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0196-6774(84)90032-4
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Complexity of the Satisfiability Problem

  2015cited by this paper
• A machine program for theorem-proving

  2011cited by this paper
• Disjoint paths in graphs

  2006cited by this paper
• Complexity Measures for Public-Key Cryptosystems

  1988influential reference
• An Algorithm for Covering Polygons with Rectangles

  1986cited by this paper
• Concurrency Control in Distributed Database Systems

  1986cited by this paper
• Trade-offs between depth and width in parallel computation

  1985cited by this paper
• Breaking Iterated Knapsacks

  1985cited by this paper
• Discrete Logarithms in Finite Fields and Their Cryptographic Significance

  1985cited by this paper
• Polynomial testing of the query "IS ab ≥ cd?" with application to finding a minimal cost reliability ratio spanning tree

  1984cited by this paper
• The complexity of completing partial Latin squares

  1984cited by this paper
• On minimal-node-cost planar embeddings

  1984cited by this paper
• On the computational complexity of the minimum-dummy-activities problem in a pert network

  1984cited by this paper
• Deciding the Inequivalence of Context-Free Grammars with 1-Letter Terminal Alphabet is Sigma-p-2-Complete

  1984cited by this paper
• The Complexity of Promise Problems with Applications to Public-Key Cryptography

  1984influential reference
• A 4n-Lower Bound on the Monotone Network Complexity of a One-Output Boolean Function

  1984cited by this paper
• An Exponential Lower Bound for One-Time-Only Branching Programs

  1984cited by this paper
• On Two Geometric Problems Related to the Traveling Salesman Problem

  1984cited by this paper
• A Linear-Tune Algorithm for Switch-Level Simulation with Race Detection in a Class of MOS VLSI Circuits

  1984cited by this paper
• A Boolean Function Requiring 3n Network Size

  1984cited by this paper
• The even-path problem for graphs and digraphs

  1984cited by this paper
• On the Complexity of Matrix Group Problems I

  1984cited by this paper
• A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem

  1984cited by this paper
• Isomorphic factorizations VIII: Bisectable trees

  1984cited by this paper
• A new polynomial-time algorithm for linear programming

  1984cited by this paper
• Eigenvalues, Expanders and Superconcentrators (Extended Abstract)

  1984cited by this paper
• Large Graphs with Given Degree and Diameter - Part I

  1984cited by this paper
• The global storage needs of a subcomputation

  1984cited by this paper
• Short Monotone Formulae for the Majority Function

  1984cited by this paper
• On the Complexity of Concurrency Control by Locking in Distributed Database Systems

  1984cited by this paper
• On Scheduling Unit-Length Jobs with Multiple Release Time/Deadline Intervals

  1984cited by this paper
• Unlabelled partition systems! optimization and complexity

  1984cited by this paper
• Intersection Graph Algorithms

  1984cited by this paper
• Computing Network Reliability in Time Polynomial in the Number of Cuts

  1984cited by this paper
• On the Algorithmic Complexity of Total Domination

  1984cited by this paper
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs

  1984cited by this paper
• Optimum Split Trees

  1984cited by this paper
• Input-output decomposition of dynamic systems is NP-complete

  1984cited by this paper
• Scheduling Precedence Graphs of Bounded Height

  1984cited by this paper
• N by N Checkers is Exptime Complete

  1984cited by this paper
• Strong NP-Hardness of Moving Many Discs

  1984cited by this paper
• Improved Dynamic Programming Algorithms for Bandwidth Minimization and the MinCut Linear Arrangement Problem

  1984cited by this paper
• Complexity of Single-Layer Routing

  1984cited by this paper
• On the np-completeness of certain network testing problems

  1984cited by this paper
• Domination, independent domination, and duality in strongly chordal graphs

  1984cited by this paper
• A Polynomial Time Algorithm for Fault Diagnosability

  1984cited by this paper
• Patent

  1984cited by this paper
• Dominating Sets for Split and Bipartite Graphs

  1984cited by this paper
• Serializability by Locking

  1984cited by this paper
• Scaling and related techniques for geometry problems

  1984cited by this paper
• On finding the exact solution of a zero-one knapsack problem

  1984cited by this paper
• Some unexpected expected behavior results for bin packing

  1984cited by this paper
• The Complexity of Two-Player Games of Incomplete Information

  1984cited by this paper
• On the Complexity of Slice Functions

  1984cited by this paper
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

  1984cited by this paper
• Lower bounds on communication complexity

  1984cited by this paper
• On the Complexity of Estimating the Size of a Test Set

  1984cited by this paper
• The impact of synchronous communication on the problem of electing a leader in a ring

  1984cited by this paper
• Threshold functions and bounded deptii monotone circuits

  1984cited by this paper
• Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems

  1984cited by this paper
• Clustering and domination in perfect graphs

  1984cited by this paper
• Backtrack: An O(1) Expected Time Algorithm for the Graph Coloring Problem

  1984cited by this paper
• Computational Aspects of VLSI

  1984cited by this paper
• Graph Problems on a Mesh-Connected Processor Array

  1984cited by this paper
• Testing the Coordination Predicate

  1984cited by this paper
• The complexity of single row routing

  1984influential reference
• Fast evaluation of logarithms in fields of characteristic two

  1984cited by this paper
• Polynomial Algorithms for Perfect Graphs

  1984cited by this paper
• On Some Variants of the Bandwidth Minimization Problem

  1984cited by this paper
• On the algorithmic complexity of coloring simple hypergraphs and steiner triple systems

  1984cited by this paper
• Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers

  1984cited by this paper
• A Lower Bound on Complexity of Branching Programs (Extended Abstract)

  1984cited by this paper
• Probabilistic Communication Complexity (Preliminary Version)

  1984cited by this paper
• The computational complexity of recognizing critical sets

  1984cited by this paper
• Linear Programming in Linear Time When the Dimension Is Fixed

  1984cited by this paper
• On Similarity and Duality of Computation (I)

  1984cited by this paper
• Problems, complete in “average” instance

  1984cited by this paper
• Reply to "Input-output decomposition of dynamic systems is NP-complete"

  1984cited by this paper
• Deadlock-Resistant Flow Control Procedures for Store-and-Forward Networks

  1984cited by this paper
• Optimal layer assignment for interconnect

  1984cited by this paper
• Constrained Optimum Communication Trees and Sensitivity Analysis

  1984cited by this paper
• On the Complexity of Iterated Shuffle

  1984cited by this paper
• An O(|E|) Time Algorithm for Computing the Reliability of a Class of Directed Networks

  1984cited by this paper
• Steiner trees, partial 2-trees, and minimum IFI networks

  1983cited by this paper
• Embedding Partial Steiner Triple Systems Is NP-Complete

  1983cited by this paper
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected

  1983cited by this paper
• The Complexity of Go

  1983cited by this paper
• Borel sets and circuit complexity

  1983cited by this paper
• Polynomial-Time Factorization of Multivariate Polynomials over Finite Fields

  1983cited by this paper
• A linear algorithm for the domination number of a series-parallel graph

  1983cited by this paper
• Scheduling file transfers in a distributed network

  1983cited by this paper
• A polynomial algorithm for the MIN CUT linear arrangement of trees

  1983cited by this paper
• On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds

  1983cited by this paper
• A nonfactorial algorithm for testing isomorphism of two graphs

  1983cited by this paper
• Integer Programming with a Fixed Number of Variables

  1983cited by this paper
• NP Completeness of Finding the Chromatic Index of Regular Graphs

  1983cited by this paper
• Solving low density subset sum problems

  1983cited by this paper
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem

  1983cited by this paper
• Concurrency Control by Locking

  1983influential reference
• Optimal Wiring of Movable Terminals

  1983cited by this paper

• Fine-Tuning Large Language Models on Quantum Optimization Problems for Circuit Generation

  2025cites this paper
• Tailored polarization-switchable VCSEL arrays for photonic Ising computing

  2025cites this paper
• Average-case thresholds for exact regularization of linear programs

  2025cites this paper
• Triangles Improve 0.878 Approximation for Maxcut

  2025cites this paper
• Linear Complexity Computation of Code Distance and Minimum Size of Trapping Sets for LDPC Codes with Bounded Treewidth

  2025cites this paper
• Maximum edge bi-clique via matrix decomposition

  2025cites this paper
• Discriminating code and set cover with k-bend paths

  2025cites this paper
• Quantum Optimization for Enhanced Combinatorial Algorithms

  2025cites this paper
• Hamiltonian path in permutation graphs

  2025cites this paper
• On Finding Randomly Planted Cliques in Arbitrary Graphs

  2025cites this paper
• Accelerating ETCD Insertion Operations through Advanced Complexity Reduction

  2025cites this paper
• How Configurable Is the Linux Kernel? Analyzing Two Decades of Feature-Model History

  2025cites this paper
• Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization

  2025cites this paper
• Comparison of two problem transformation-based methods in detecting the best performing branch-and-bound procedures for the RCPSP

  2025cites this paper
• Sliding Mode Control‐Like Accelerated Coherent Ising Machine

  2025cites this paper
• How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs

  2025cites this paper
• Two-stage hybrid flow shop scheduling with sequence-dependent setup times in semiconductor manufacturing: A customized variable neighborhood search

  2025cites this paper
• A swarm intelligence approach to minimum weight independent dominating set problem

  2025cites this paper
• Optimal Decision Tree Pruning Revisited: Algorithms and Complexity

  2025cites this paper
• The Hamiltonian Property of the Data Center Network DPCell

  2025cites this paper
• Extending battery lifespan in IoT extreme sensor networks through collaborative reinforcement learning-powered task offloading

  2025cites this paper
• Recognizing integrality of weighted rectangles partitions

  2025cites this paper
• Efficient Fabric Cutting for Customized Curtains: Minimizing Waste and Resource Use

  2024cites this paper
• Game Theory with Simulation in the Presence of Unpredictable Randomisation

  2024cites this paper
• Reusing d-DNNFs for Efficient Feature-Model Counting

  2024cites this paper
• Graph Computation with Adaptive Granularity

  2024cites this paper
• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs

  2024cites this paper
• Online Offloading for Energy-Efficient and Delay-Aware MEC Systems With Cellular-Connected UAVs

  2024cites this paper
• Computing Optimal Commitments to Strategies and Outcome-Conditional Utility Transfers

  2024cites this paper
• Answering Spatial Density Queries Under Local Differential Privacy

  2024cites this paper
• Further split graphs known to be Class 1 and a characterization of subgraph-overfull split graphs

  2024cites this paper
• On the Variants of Subset Sum: Projected and Unbounded

  2023cites this paper
• Is P equal to NP? Answer and Method to solve puzzles with God's algorithm

  2023cites this paper
• Effective Computation of a Feedback Arc Set Using PageRank

  2023cites this paper
• Network Flow Problems with Electric Vehicles

  2023cites this paper
• On Functional Observability and Structural Functional Observability

  2023cites this paper
• Polyhedral approach to weighted connected matchings in general graphs

  2023cites this paper
• Parameterized Model-checking of Discrete-Timed Networks and Symmetric-Broadcast Systems

  2023cites this paper
• Revising Johnson’s table for the 21st century – current table

  2022cites this paper
• Preventing Small $\mathbf{(s,t)}$-Cuts by Protecting Edges

  2021influential citation
• Towards Informed Partitioning for Load Balancing: a Proof-of-Concept

  2021cites this paper
• Combinatorial Optimization withPointer Networks and Reinforcement Learning Kombinatorisk Optimeringmed Pointer Networks och Reinforcement Learning

  2021cites this paper
• The Price of Defense

  2021influential citation
• Pattern Recognition: 12th Mexican Conference, MCPR 2020, Morelia, Mexico, June 24–27, 2020, Proceedings

  2020cites this paper
• On the Behavior of Parallel Island Model Genetic Algorithms

  2020cites this paper
• MIP Formulations for the Maximum Expected Value Partially Successful Path Problem

  2020cites this paper
• Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays

  2018cites this paper
• Levelable Sets and the Algebraic Structure of Parameterizations

  2017cites this paper
• Discretized Approaches to Schematization

  2016cites this paper
• Hamilton cycles in hypergraphs below the Dirac threshold

  2016cites this paper
• Multiwinner Analogues of Plurality Rule: Axiomatic and Algorithmic Perspectives

  2016cites this paper
• Absorbing Random-Walk Centrality: Theory and Algorithms

  2015cites this paper
• A Unified Framework for Event Summarization and Rare Event Detection from Multiple Views

  2015cites this paper
• New Wine into Old Wineskins: A Survey of Some Pebbling Classics with Supplemental Results

  2015cites this paper
• Analysis of complex disease association studies : a practical guide

  2011cites this paper
• New Candidates Welcome! Possible Winners with respect to the Addition of New Candidates

  2011cites this paper
• Finding optimal solutions for covering and matching problems

  2010cites this paper
• Arithmetization: a New Method in Structural Complexity Theory

  2010cites this paper
• Conditional Lower Bounds on the Complexity of Probabilistic Inference

  2009cites this paper
• On the graph isomorphism problem

  2008cites this paper
• Workshop: Complexity, Expressibility, and Decidability in Automated Reasoning - CEDAR'08

  2008cites this paper
• From Universal Laws of Cognition to Specific Cognitive Models Candidate Principles 1: Scale Invariance Candidate Law 2: the Simplicity Principle

  2008cites this paper
• Transactions on Computational Biology and Bioinformatics 1 Comparing Genomes with Duplications: a Computational Complexity Point of View

  2007cites this paper
• Algorithms and Experiments for Parameterized Approaches to Hard Graph Problems

  2007cites this paper
• Problem-centric scheduling for heterogeneous computing systems

  2007cites this paper
• A greedier approach for finding tag SNPs

  2006cites this paper
• Dynamic Load Balancing for the Distributed Mining of Molecular Structures

  2006cites this paper
• Algorithm design techniques for parameterized graph modification problems

  2006cites this paper
• N I / 06 04 01 7 v 3 7 D ec 2 00 6 AS Relationships : Inference and Validation

  2006cites this paper
• Canonical forms for labelled trees and their applications in frequent subtree mining

  2005cites this paper
• An introduction to clobber.

  2005cites this paper
• Taxonomies of Visual Programming P and rogram Visualization

  2003cites this paper
• Discovery of Transcription Factor Binding Sites

  2003cites this paper
• A disproof of Henning's conjecture on irredundance perfect graphs

  2002cites this paper
• An overview of constraint-based path selection algorithms for QoS routing

  2002cites this paper
• Models and Approximation Algorithms for Channel Assignment in Radio Networks

  2001cites this paper
• Illusions in reasoning about consistency.

  2000cites this paper
• Graph Layout for Applications in Compiler Construction

  1999cites this paper
• A multiobjective hybrid genetic algorithm for the capacitated multipoint network design problem

  1999influential citation
• Optimal On-Line Scheduling of Parallel Jobs with Dependencies

  1998cites this paper
• BOUNDED DEGREE SPANNING TREES

  1997cites this paper
• Multi-prover Encoding Schemes and Three-prover Proof Systems

  1996cites this paper
• Mixed Searching and Proper-Path-Width

  1995cites this paper
• Graph Sandwich Problems

  1995cites this paper
• Uni-directional Alternating Group Graphs

  1995cites this paper
• Propositional Circumscription and Extended Closed-World Reasoning are IIp2-Complete

  1993cites this paper
• Biconnectivity approximations and graph carvings

  1992influential citation
• Taxonomies of Visual Programming P and rogram Visualization

  1989cites this paper
• Finding Maximum Cliques on Circular-Arc Graphs

  1987cites this paper
• Efficient Algorithms for Domination and Hamilton Circuit Problems on Permutation Graphs

  1987cites this paper
• Bard: Better Automated Redistricting

  year unknowncites this paper
• Bard: Better Automated Redistricting

  year unknowncites this paper
• Bard: Better Automated Redistricting

  year unknowncites this paper
• Graphical Proof Theory I: Sequent Calculi operating on Undirected Graphs

  year unknowncites this paper
• Durham E-Theses Rank Lower Bounds in Propositional Proof Systems Based on Integer Linear Programming Methods

  year unknowncites this paper
• Identifying Active Transcription Factors and Kinases from Expression Data Using Pathway Queries

  year unknowncites this paper
• De Novo Discovery of Mutated Driver Pathways in Cancer Material Supplemental Related Content

  year unknowncites this paper
• Transactions on Computational Biology and Bioinformatics 1 Comparing Genomes with Duplications: a Computational Complexity Point of View

  year unknowncites this paper
• Article in Press Information and Computation Treewidth Computations I. Upper Bounds ୋ

  year unknowncites this paper
• Approximation Algorithms for Directed Steiner Problems

  year unknowncites this paper