Faster access than browser!
40 relations: Approximation algorithm, Asymptotic computational complexity, Boolean satisfiability problem, Complete coloring, Complexity class, Computers and Intractability, Crossing number (graph theory), David Johnson, Deaths in March 2016, Empirical algorithmics, Frederick W. Lanchester Prize, Hamiltonian path problem, Knapsack problem, Knuth Prize, Linear programming, List of Amherst College people, List of computer scientists, List of Fellows of the Association for Computing Machinery, List of members of the National Academy of Engineering (Computer science), List of multiple discoveries, List of people by Erdős number, Longest common subsequence problem, Maximum common induced subgraph, Michael Garey, Michael J. Fischer, NP-completeness, NP-hardness, Polynomial hierarchy, Post correspondence problem, Pursuit-evasion, Quadratic assignment problem, Rainbow matching, Set packing, Shortest total path length spanning tree, Subset sum problem, Topological graph, Václav Chvátal, WalkSAT, 2016 in the United States, 3-partition problem.
Approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to NP-hard optimization problems with provable guarantees on the distance of the returned solution to the optimal one.
New!!: David S. Johnson and Approximation algorithm · See more »
Asymptotic computational complexity
In computational complexity theory, asymptotic computational complexity is the usage of asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O notation.
New!!: David S. Johnson and Asymptotic computational complexity · See more »
Boolean satisfiability problem
In computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated as SATISFIABILITY or SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.
New!!: David S. Johnson and Boolean satisfiability problem · See more »
Complete coloring
In graph theory, complete coloring is the opposite of harmonious coloring in the sense that it is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices.
New!!: David S. Johnson and Complete coloring · See more »
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.
New!!: David S. Johnson and Complexity class · See more »
Computers and Intractability
In computer science, more specifically computational complexity theory, Computers and Intractability: A Guide to the Theory of NP-Completeness is an influential textbook by Michael Garey and David S. Johnson.
New!!: David S. Johnson and Computers and Intractability · See more »
Crossing number (graph theory)
In graph theory, the crossing number of a graph is the lowest number of edge crossings of a plane drawing of the graph.
New!!: David S. Johnson and Crossing number (graph theory) · See more »
David Johnson
David, Dave or Davey Johnson may refer to.
New!!: David S. Johnson and David Johnson · See more »
Deaths in March 2016
The following is a list of notable deaths in March 2016.
New!!: David S. Johnson and Deaths in March 2016 · See more »
Empirical algorithmics
In computer science, empirical algorithmics (or experimental algorithmics) is the practice of using empirical methods to study the behavior of algorithms.
New!!: David S. Johnson and Empirical algorithmics · See more »
Frederick W. Lanchester Prize
The Frederick W. Lanchester Prize is an Institute for Operations Research and the Management Sciences prize (U.S. $5,000 cash prize and medallion) given for the best contribution to operations research and the management sciences published in English.
New!!: David S. Johnson and Frederick W. Lanchester Prize · See more »
Hamiltonian path problem
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected).
New!!: David S. Johnson and Hamiltonian path problem · See more »
Knapsack problem
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
New!!: David S. Johnson and Knapsack problem · See more »
Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.
New!!: David S. Johnson and Knuth Prize · See more »
Linear programming
Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.
New!!: David S. Johnson and Linear programming · See more »
List of Amherst College people
This is a list of some notable people affiliated with Amherst College.
New!!: David S. Johnson and List of Amherst College people · See more »
List of computer scientists
This is a list of computer scientists, people who do work in computer science, in particular researchers and authors.
New!!: David S. Johnson and List of computer scientists · See more »
List of Fellows of the Association for Computing Machinery
This article lists ACM Fellows, an award and fellowship granted by the Association for Computing Machinery (ACM) as its highest honorary grade of membership, reserved for ACM members who have exhibited "professional excellence" in their "technical, professional and leadership contributions" Since 1993, the people that have been elected as Fellows are listed below.
New!!: David S. Johnson and List of Fellows of the Association for Computing Machinery · See more »
List of members of the National Academy of Engineering (Computer science)
This list is a subsection of the List of members of the National Academy of Engineering, which includes over 2,000 current members of the United States National Academy of Engineering, each of whom is affiliated with one of 12 disciplinary sections.
New!!: David S. Johnson and List of members of the National Academy of Engineering (Computer science) · See more »
List of multiple discoveries
Historians and sociologists have remarked the occurrence, in science, of "multiple independent discovery".
New!!: David S. Johnson and List of multiple discoveries · See more »
List of people by Erdős number
Paul Erdős (1913–1996) was the most prolifically published mathematician of all time.
New!!: David S. Johnson and List of people by Erdős number · See more »
Longest common subsequence problem
The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences).
New!!: David S. Johnson and Longest common subsequence problem · See more »
Maximum common induced subgraph
In graph theory and theoretical computer science, a maximum common induced subgraph of two graphs G and H is a graph that is an induced subgraph of both G and H, and that has as many vertices as possible.
New!!: David S. Johnson and Maximum common induced subgraph · See more »
Michael Garey
Michael Randolph Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractability: A Guide to the Theory of NP-completeness.
New!!: David S. Johnson and Michael Garey · See more »
Michael J. Fischer
Michael John Fischer (born 1942) is a computer scientist who works in the fields of distributed computing, parallel computing, cryptography, algorithms and data structures, and computational complexity.
New!!: David S. Johnson and Michael J. Fischer · See more »
NP-completeness
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
New!!: David S. Johnson and NP-completeness · See more »
NP-hardness
NP-hardness (''n''on-deterministic ''p''olynomial-time hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP".
New!!: David S. Johnson and NP-hardness · See more »
Polynomial hierarchy
In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.
New!!: David S. Johnson and Polynomial hierarchy · See more »
Post correspondence problem
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.
New!!: David S. Johnson and Post correspondence problem · See more »
Pursuit-evasion
Pursuit-evasion (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment.
New!!: David S. Johnson and Pursuit-evasion · See more »
Quadratic assignment problem
The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems.
New!!: David S. Johnson and Quadratic assignment problem · See more »
Rainbow matching
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.
New!!: David S. Johnson and Rainbow matching · See more »
Set packing
Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.
New!!: David S. Johnson and Set packing · See more »
Shortest total path length spanning tree
In computer science, the shortest total path length spanning tree is, given an n-node undirected graph G(V, E); positive integer B, does there exist a spanning tree T(V, F) of G such that the sum over all pairs of nodes u and v of the length of the path between u and v in T is no greater than B?.
New!!: David S. Johnson and Shortest total path length spanning tree · See more »
Subset sum problem
In computer science, the subset sum problem is an important problem in complexity theory and cryptography.
New!!: David S. Johnson and Subset sum problem · See more »
Topological graph
In mathematics, a topological graph is a representation of a graph in the plane, where the ''vertices'' of the graph are represented by distinct points and the ''edges'' by Jordan arcs (connected pieces of ''Jordan curves'') joining the corresponding pairs of points.
New!!: David S. Johnson and Topological graph · See more »
Václav Chvátal
Václav (Vašek) Chvátal (is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Canada. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.
New!!: David S. Johnson and Václav Chvátal · See more »
WalkSAT
In computer science, GSAT and WalkSAT are local search algorithms to solve Boolean satisfiability problems.
New!!: David S. Johnson and WalkSAT · See more »
2016 in the United States
Events in the year 2016 in the United States.
New!!: David S. Johnson and 2016 in the United States · See more »
3-partition problem
The 3-partition problem is an NP-complete problem in computer science.
New!!: David S. Johnson and 3-partition problem · See more »
Redirects here:
D. S. Johnson, David Stifler Johnson.
References
[1] https://en.wikipedia.org/wiki/David_S._Johnson
