Share This
table started by
narphorium for the Computer Science Base
There is no user-contributed description yet.
Add More Topics
Save this view to a base, or just for yourself.
53 Computational problem topics matching:
Filter this Collection| x name | x image | x article |
|---|---|---|
| x 3-dimensional matching |
In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (a.k.a. 2-dimensional matching) to 3-uniform hypergraphs. Finding a largest 3-dimensional matching is a well-known NP-hard problem in...
|
|
| x 3-partition problem |
The 3-partition problem is an NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. More precisely, given a multiset S of n = 3 m positive...
|
|
| x 3SAT | ||
| x Bin packing problem |
In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used.
There are...
|
|
| x Bipartite dimension |
In the mathematical field of graph theory, the bipartite dimension of a graph G = (V, E) is the minimum number of bicliques, that is, complete bipartite subgraphs, needed to cover all edges in E. A collection of bicliques covering all edges in G is...
|
|
| x Boolean conjunctive query |
In the theory of relational databases, a Boolean conjunctive query is a conjunctive query without distinguished predicates, i.e., a query in the form , where each Ri is a relation symbol and each ti is a tuple of variables and constants; the number...
|
|
| x Boolean satisfiability problem |
Satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE. Equally important is to determine whether no such assignments exist, which would imply...
|
|
| x Bottleneck traveling salesman problem |
The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. It is stated as follows: Find the Hamiltonian cycle in a weighted graph which minimizes the weight of the most weighty edge of the...
|
|
| x Clique |
In graph theory, a clique in an undirected graph G = (V, E) is a subset of the vertex set C ⊆ V, such that for every two vertices in C, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete ...
|
|
| x 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. Equivalently, a complete coloring is minimal in the...
|
|
| x Degree constrained spanning tree |
In graph theory, a degree-constrained spanning tree is a spanning tree where the maximum vertex degree is limited to a certain constant k. The degree-constrained spanning tree problem is to determine whether a particular graph has such a spanning...
|
|
| x Domatic number |
In graph theory, a domatic partition of a graph G = (V,E) is a partition of V into disjoint sets V1, V2,...,VK such that each Vi is a dominating set for G. The figure on the rights shows a domatic partition of a graph; here the dominating set V1...
|
|
| x Dominating set problem |
The dominating set problem is an NP-complete problem in graph theory.
An instance of the dominating set problem consists of:
The problem is to determine whether there is a dominating set of size K or less for G. That is, we want to know if there is...
|
|
| x Exact cover |
In mathematics, given a collection of subsets of a set X, an exact cover is a subcollection of such that each element in X is contained in exactly one subset in . One says that each element in X is covered by exactly one subset in . An exact...
|
|
| x Feedback arc set |
In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG). One way to do this is simply to drop...
|
|
| x Feedback vertex set |
In computational complexity theory, the feedback vertex set problem is a graph-theoretical NP-complete problem. It was among the first problems shown to be NP-complete. The decision problem can be formalized as follows:
Karp originally showed the...
|
|
| x Flow Shop Scheduling Problem |
Flow Shop Scheduling Problems, or FSPs, are a class of Group Shop Scheduling Problems in which the operations of every job must be processed on machines 1,2,...,m in this same order. A special case of FSPs are Permutation Flow Shop Scheduling...
|
|
| x Generalized Assignment Problem |
In applied mathematics, the maximum generalized assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both tasks and agents have a size. Moreover, the size of each task...
|
|
| x Graph coloring |
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a...
|
|
| x Graph homomorphism |
In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices.
A graph homomorphism f from a graph G = (V,E) to a graph G'...
|
|
| x Graph partition |
The graph partitioning problem in mathematics consists of dividing a graph into pieces, such that the pieces are of about the same size and there are few connections between the pieces.
Consider a graph G(V,E), where V denotes the set of vertices...
|
|
| x Hamiltonian completion |
The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian.
The problem is clearly NP-hard in general case (since its solution gives an answer to the NP-complete problem of determining whether...
|
|
| x 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 or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both...
|
|
| x Hitting set |
The hitting set problem is an NP-complete problem in set theory. For a given list of sets, a hitting set is a set of elements so that each set in the given list is 'touched' by the hitting set. In the hitting set problem, the task is to find a small...
|
|
| x Independent set problem |
In mathematics, the independent set problem (Independent Set or IS) is a well-known problem in graph theory. The independent set problem is known to be NP-complete. It is closely related to the clique problem.
In a simple graph G, an independent set...
|
|
| x Induced path |
|
In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge...
|
| x 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 a given...
|
|
| x Linear programming |
|
In mathematics, linear programming (LP) is a technique for optimization of a linear objective function, subject to linear equality and linear inequality constraints. Informally, linear programming determines the way to achieve the best outcome (such...
|
| x Longest common subsequence problem |
The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). It is a classic computer science problem, the basis of diff (a file comparison program that outputs the...
|
|
| x Longest path problem |
In graph theory, the longest path problem is to find a simple path of maximum length in a given graph. Unlike the shortest path problem, which can be solved in polynomial time in graphs without negative cycles, this problem is NP-complete which...
|
|
| x Maximum cut |
For a graph, a maximum cut is a cut whose size is not smaller than the size of any other cut. The problem of finding a maximum cut in a graph is known as the max-cut problem.
The problem can be stated simply as follows. One wants a subset S of the...
|
|
| x Maximum leaf spanning tree |
Maximum Leaf Spanning Tree
Input: n-node undirected graph G(V,E); positive integer k
|
|
| x Maximum satisfiability problem |
Satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE.
The Maximum Satisfiability problem (MAX-SAT) asks for the maximum number of clauses which...
|
|
| x Metric dimension |
In graph theory, the metric dimension of a graph G is the minimum number of vertices in a subset S of G such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP...
|
|
| x Minimum degree spanning tree |
In graph theory, for a connected graph G, a spanning tree T is a subgraph of G with the least number of edges that still spans G. A number of properties can be proved about T. T is acyclic, has ( | V | − 1) edges where V is the number of vertices in...
|
|
| x Monochromatic triangle |
The monochromatic triangle problem is a decision problem that is known to be NP-complete.
Input: An n-node undirected graph G(V,E) with node set V and edge set E.
Question: Can the edges, E, of G be partitioned into two disjoint sets E1 and E2, such...
|
|
| x Multiprocessor scheduling |
In computer science, multiprocessor scheduling is an NP-Complete optimization problem. The problem statement is: "Given a set J of jobs where job ji has length li and a number of processors mi, what is the minimum possible time required to schedule...
|
|
| x One-in-three 3SAT |
In computational complexity theory, one-in-three 3SAT (also known variously as 1-in-3 SAT and exactly-1 3SAT) is an NP-complete problem. The problem is a variant of the 3-satisfiability problem (3SAT). Like 3SAT, the input instance is a collection...
|
|
| x Partition problem |
In computer science, the partition problem is an NP-complete problem. The problem is to decide whether a given multiset of integers can be partitioned into two "halves" that have the same sum. More precisely, given a multiset S of integers, is there...
|
|
| x Post correspondence problem |
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.
The input of the...
|
|
| x Quadratic assignment problem |
The quadratic assignment problem (QAP) is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems.
The problem models the...
|
|
| x Serializability |
In databases, transaction processing (transaction management), and various transactional applications, both centralized and distributed, a transaction schedule (history) is serializable, has the Serializability property, if its outcome (the...
|
|
| x Set cover problem |
|
The set covering problem is a classical question in computer science and complexity theory. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.
As input you are given...
|
| x 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.
Suppose we have a finite set S and a list of subsets of S. Then, the set packing problem asks if some...
|
|
| x Set splitting problem |
In computational complexity theory, the Set Splitting problem is the following decision problem: given a family F of subsets of a finite set S, whether there exists a partition of S in two subsets S1, S2 such that all elements of F are split by this...
|
|
| x Shortest common supersequence |
This shortest common supersequence problem is closely related to the longest common subsequence problem. Given two sequences X = and Y = , a sequence U = is a common supersequence of X and Y if U is a...
|
|
| x Sparse approximation |
Sparse approximation is the problem of finding a signal or vector estimate with sparseness property, that is having a small number of nonzero elements, that satisfies (approximately) a system of equations.
For example, consider a linear system of...
|
|
| x Steiner tree |
|
The Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization.
The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of points (vertices), interconnect them by a...
|
| x Subgraph isomorphism problem |
In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. Subgraph isomorphism is a...
|
|
| x Subset sum problem |
In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set of integers, does the sum of some non-empty subset equal exactly zero? For example, given the set { −7, −3, ...
|
|
| x Travelling salesman problem |
|
The Travelling Salesman Problem (TSP) is a problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that...
|
| x Vehicle routing problem |
The vehicle routing problem (VRP) is a combinatorial optimization and nonlinear programming problem seeking to service a number of customers with a fleet of vehicles. Proposed by Dantzig and Ramser in 1959, VRP is an important problem in the fields...
|
|
| x Vertex cover problem |
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical optimization...
|
|
