Computers And Intractability A Guide To The Theory Of Np Completeness

By B. Eggers. 2016

7,333 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Text Categorization as a Graph Classification Problem (2015, background): “In particular, the general problem of subgraph matching , which deﬁnes an isomorphism between a graph and a subgraph and is NP-complete (Garey and Johnson, 1990), can be reduced to a polynomial problem when node labels are unique.”
Learning a SAT Solver from Single-Bit Supervision (2018, background): “(5)See (Lewis, 1983) for an overview of these problems as well as the standard encodings.”
Assortment Optimization Under Variants of the Nested Logit Model (2014, methodology): “To establish the NP-hardness of problem (2), Theorem 5 below shows that any instance of the partition problem, which is a well-known NP-hard problem as established in Garey and Johnson (1979), can be reduced to an instance of the assortment feasibility problem. Rusmevichientong, Shmoys and Topaloglu”
Quantum circuits and low-degree polynomials over F2 (2016, background): “This is an NP-complete problem [21], but luckily an approximation h (cid:48) ( f ) ≤ 3 h ( f ) can be found in polynomial time (approximating h ( f ) any better than this is NP-hard [28], assuming the Unique Games Conjecture from complexity theory).”
Optimization Approaches for the Traveling Salesman Problem with Drone (2016, background): “Although the traveling salesman problem is NP-hard [Garey and Johnson, 1979], it is a well-researched problem and instances of up to several hundreds of nodes can be solved quickly with a state of the art TSP solver such as Concorde [Applegate et al., 2001].”
Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning (2016, unknown): “This is often related to the kth-shortest-path problem, which is NP-hard [118].”
Security Arguments for Digital Signatures and Blind Signatures (2015, methodology): “Stated in a more accurate way, this approach proposes computational reductions to well-established problems, such as factorization, RSA [49], the discrete logarithm problem, or any NP-complete problem [24].”
SeeDB: Efficient Data-Driven Visualization Recommendations to Support Visual Analytics (2015, background): “Notice that the above problem is isomorphic to the NP-Hard bin-packing problem [18].”
Automated Planning and Acting (2016, background): “There are several theoretical models of nondeterministic choice that are more-or-less equivalent mathematically [213, 464, 131].”
Electric vehicle fleet management in smart grids: A review of services, optimization and control aspects (2016, unknown): “This problem can be classified as a NP-hard problem [101].”
Ant Colony Optimization: Overview and Recent Advances (2018, background): “The notion of problem hardness is captured by the theory of computational complexity [79, 123] and for many important problems it is well known that they are NP-hard, that is, the time needed to solve an instance in the worst case grows exponentially with instance size.”
An Optimization Spiking Neural P System for Approximately Solving Combinatorial Optimization Problems (2014, background): “The knapsack problem, a well-known NP-complete combinatorial optimization problem, can be described as selecting from among various items that are most profitable, given that the knapsack has limited capacity.(25,32) The knapsack problem is to select a subset from the given number of items so as to ”