|
Permutation Graph
In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation (up to permutation symmetry) if it is prime with respect to the modular decomposition. Definition and characterization If \rho = (\sigma_1,\sigma_2,...,\sigma_n) is any permutation of the numbers from 1 to n, then one may define a permutation graph from \sigma in which there are n vertices v_1, v_2, ..., v_n, and in which there is an edge v_i v_j for any two indices i and j for which i\sigma_j. That is, two indices i and j determine an edge in the permutation graph exactly when they determine an inversion in the permutatio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Permutation Graph
In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation (up to permutation symmetry) if it is prime with respect to the modular decomposition. Definition and characterization If \rho = (\sigma_1,\sigma_2,...,\sigma_n) is any permutation of the numbers from 1 to n, then one may define a permutation graph from \sigma in which there are n vertices v_1, v_2, ..., v_n, and in which there is an edge v_i v_j for any two indices i and j for which i\sigma_j. That is, two indices i and j determine an edge in the permutation graph exactly when they determine an inversion in the permutatio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Comparability Graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order. Definitions and characterization For any strict partially ordered set , the comparability graph of is the graph of which the vertices are the elements of and the edges are those pairs of elements such that . That is, for a partially ordered set, take the directed acyclic graph, apply transitive closure, and remove orientation. Equivalently, a comparability graph is a graph that has a transitive orientation, an assignment of directions to the edges of the graph (i.e. an orientation of the graph) such that the adjacency relation of the resulting directe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Vertex Separator
In graph theory, a vertex subset is a vertex separator (or vertex cut, separating set) for nonadjacent vertices and if the removal of from the graph separates and into distinct connected components. Examples Consider a grid graph with rows and columns; the total number of vertices is . For instance, in the illustration, , , and . If is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing to be any of these central rows or columns, and removing from the graph, partitions the graph into two smaller connected subgraphs and , each of which has at most vertices. If (as in the illustration), then choosing a central column will give a separator with r \leq \sqrt vertices, and similarly if then choosing a central row will give a separator with at most \sqrt vertices. Thus, every grid graph has ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pathwidth
In graph theory, a path decomposition of a graph is, informally, a representation of as a "thickened" path graph, and the pathwidth of is a number that measures how much the path was thickened to form . More formally, a path-decomposition is a sequence of subsets of vertices of such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets,. and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness (one less than the maximum clique size in an interval supergraph of ), vertex separation number, or node searching number. Pathwidth and path-decompositions are closely analogous to treewidth and tree decompositions. They play a key role in the theory of graph minors: the families of graphs that are closed under graph minors and do not include all forests may be characterized as having bounded pathwidth, and the "vortices ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly are called '' -trees'', and the graphs with treewidth at most are called '' partial -trees''. Many other well-studied graph families also have bounded treewidth. Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a tree decomposition of the graph, in terms of the size of the largest clique in a chordal completion of the graph, in terms of the maximum order of a haven describing a strategy for a pursuit–evasion game on the graph, or in terms of the maximum order of a bramble, a collection of connected subgraphs that all touch each other. Treewidth is commonly used as a pa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Independent Set (graph Theory)
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in S. A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening. A maximal independent set is an independent set that is not a proper subset of any other independent set. A maximum independent set is an independent set of largest possible size for a given graph G. This size is called the independence number of ''G'' and is usually denoted by \alpha(G). The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NP-hard problem. As such ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial Time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expresse ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clique Problem
In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique (a clique with the largest possible number of vertices), finding a maximum weight clique in a weighted graph, listing all maximal cliques (cliques that cannot be enlarged), and solving the decision problem of testing whether a graph contains a clique larger than a given size. The clique problem arises in the following real-world setting. Consider a social network, where the graph's vertices represent people, and the graph's edges represent mutual acquaintance. Then a clique represents a subset of people who all know each other, and algorithms for finding cliques can be used to discover these groups of m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Longest Increasing Subsequence
In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. Longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics. The longest increasing subsequence problem is solvable in time O(n \log n), where n denotes the length of the input sequence. Example In the first 16 terms of the binary Van der Corput sequence :0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 a longest increasing subsequence is :0, 2, 6, 9, 11, 15. This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not the only solution: for instance, :0, 4, 6, 9, 11, 15 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clique (graph Theory)
In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied. Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by , the term ''clique'' comes from , who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinf ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-complete
In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. # the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified. The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a de ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Perfect Graph
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfect if and only if for all S\subseteq V we have \chi(G =\omega(G . The perfect graphs include many important families of graphs and serve to unify results relating colorings and cliques in those families. For instance, in all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time. In addition, several important min-max theorems in combinatorics, such as Dilworth's theorem, can be expressed in terms of the perfection of certain associated graphs. A graph G is 1-perfect if and only if \chi(G)=\omega(G). Then, G is perfect if and only if every induced subgraph of G is 1-perfect. Properties * By the perfect graph theorem, a graph G is perfect if and on ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
