|
Clique-width
In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum number of labels needed to construct by means of the following 4 operations : #Creation of a new vertex with label (denoted by ) #Disjoint union of two labeled graphs and (denoted by G \oplus H) #Joining by an edge every vertex labeled to every vertex labeled (denoted by ), where #Renaming label to label (denoted by ) Graphs of bounded clique-width include the cographs and distance-hereditary graphs. Although it is NP-hard to compute the clique-width when it is unbounded, and unknown whether it can be computed in polynomial time when it is bounded, efficient approximation algorithms for clique-width are known. Based on these algorithms and on Courcelle's theorem, many graph optimization problems that are NP-hard for arbitrary graph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clique-width Construction
In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum number of labels needed to construct by means of the following 4 operations : #Creation of a new vertex with label (denoted by ) #Disjoint union of two labeled graphs and (denoted by G \oplus H) #Joining by an edge every vertex labeled to every vertex labeled (denoted by ), where #Renaming label to label (denoted by ) Graphs of bounded clique-width include the cographs and distance-hereditary graphs. Although it is NP-hard to compute the clique-width when it is unbounded, and unknown whether it can be computed in polynomial time when it is bounded, efficient approximation algorithms for clique-width are known. Based on these algorithms and on Courcelle's theorem, many graph optimization problems that are NP-hard for arbitrary gr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rank-width
Rank-width is a graph width parameter used in graph theory and parameterized complexity. This parameter indicates the minimum integer ''k'' for a given graph ''G'' so that the tree can be decomposed into tree-like structures by splitting its vertices such that each cut induces a matrix of rank at most ''k''. Even though there are various other width parameters that have been shown to be very useful, but some of them like treewidth (or clique-width In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum num ...) are bounded for only for sparse (or dense) graphs. For the dense graphs, where clique-width can be used, there is no efficient algorithm deciding this parameter. This is where rank-width comes to the picture. There exists an algorithm running in polynomial time that decides if the rank-w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Power
In graph theory, a branch of mathematics, the th power of an undirected graph is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in is at most . Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: is called the ''square'' of , is called the ''cube'' of , etc. Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph. Properties If a graph has diameter , then its -th power is the complete graph. If a graph family has bounded clique-width, then so do its -th powers for any fixed . Coloring Graph coloring on the square of a graph may be used to assign frequencies to the participants of wireless communication networks so that no two participants interfere with each other at any of their common neighbors, and to find graph drawings with high angular resolution. Both the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Parameterized Complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. The first systematic work on parameterized complexity was done by . Under the assumption that P ≠NP, there exist many natural problems that require superpolynomial running time when complexity is measured in terms of the input size only, but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter . Hence, if is fixed at a small value and the growth of the function over is relatively small then such p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Split Decomposition
In graph theory, a split of an undirected graph is a Cut (graph theory), cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms. Splits and split decompositions were first introduced by , who also studied variants of the same notions for directed graphs.. Definitions A Cut (graph theory), cut of an undirected graph is a partition of the vertices into two nonempty subsets, the sides of the cut. The subset of edges that have one endpoint in each side is called a cut-set. When a cut-set forms a complete bipartite graph, its cut is called a split. Thus, a split can be described as a partition of the vertices of the graph into two subsets an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
χ-bounded In graph theory, a \chi-bounded family \mathcal of graphs is one for which there is some function c such that, for every integer t the graphs in \mathcal with t=\omega(G) (clique number) can be colored with at most c(t) colors. This concept and its notation were formulated by András Gyárfás. The use of the Greek letter chi in the term \chi-bounded is based on the fact that the chromatic number of a graph G is commonly denoted \chi(G). Nontriviality It is not true that the family of all graphs is \chi-bounded. As and showed, there exist triangle-free graphs of arbitrarily large chromatic number, so for these graphs it is not possible to define a finite value of t(3). Thus, \chi-boundedness is a nontrivial concept, true for some graph families and false for others. Specific classes Every class of graphs of bounded chromatic number is (trivially) \chi-bounded, with c(t) equal to the bound on the chromatic number. This includes, for instance, the planar graphs, the bipartite gr ... |
