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 |
In computer science, satisfiability (often written in all capitals or abbreviated SAT) 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...
|
|
| 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 the mathematical area of graph theory, a clique (pronounced /ˈkliːk/ or /ˈklɪk/) in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of...
|
|
| 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 right 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 the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph. The...
|
|
| x Flow Shop Scheduling Problem |
Flow Shop Scheduling Problems, or FSPs, are a class of scheduling problems with a work shop or group shop in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of machines or with other resources 1...
|
|
| 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 |
In mathematics, the graph partition problem is defined on data represented in the form of a graph G= (V,E), with V vertices and E edges, such that it is possible to partition G into smaller components with specific properties. For instance, a k-way...
|
|
| 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 or equal to...
|
|
| x Linear programming |
|
Linear programming (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear...
|
| 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). Note that subsequence is different from a substring, see substring vs. subsequence. It is a classic...
|
|
| x Longest path problem |
In the mathematical discipline of graph theory, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices. Unlike the shortest path problem,...
|
|
| x Maximum cut |
For a graph, a maximum cut is a cut whose size is at least 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 vertex...
|
|
| x Maximum leaf spanning tree |
Maximum Leaf Spanning Tree
Input: n-node undirected graph G(V,E); positive integer k
|
|
| x Maximum satisfiability problem |
In computational complexity theory, the Maximum Satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given Boolean formula, that can be satisfied by some assignment. It is an FNP generalization of SAT....
|
|
| 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-hard 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 all...
|
|
| 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 the task of deciding whether a given multiset of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the...
|
|
| 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 concurrency control of databases, transaction processing (transaction management), and various transactional applications (e.g., transactional memory and software transactional memory), both centralized and distributed, a transaction schedule is...
|
|
| x Set cover problem |
|
The set covering problem (SCP) 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. It was also one of...
|
| 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, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are...
|
|
| x Shortest common supersequence |
In computer science, the shortest common supersequence problem is a problem closely related to the longest common subsequence problem. Given two sequences X = and Y = , a sequence U = is a common...
|
|
| x Sparse approximation |
Sparse approximation (also referred to as sparse decomposition) is the problem of estimating a sparse multi-dimensional vector, satisfying a linear system of equations given high-dimensional observed data and a design matrix. Sparse approximation...
|
|
| x Steiner tree |
|
The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the...
|
| 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, is there a non-empty subset whose sum is zero? For example, given the set { −7, −3, −2, 5, 8},...
|
|
| x Travelling salesman problem |
|
The travelling salesman problem (TSP) is an NP-hard 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 the shortest possible...
|
| x Vehicle routing problem |
|
The vehicle routing problem (VRP) is a combinatorial optimization and integer 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 of...
|
| 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...
|
|
