In mathematics, a minimum bottleneck spanning tree (MBST) in an undirected graph is a spanning tree in which the most expensive edge is as cheap as possible. A bottleneck edge is the highest weighted edge in a spanning tree. A spanning tree is a minimum bottleneck spanning tree if the graph does not contain a spanning tree with a smaller bottleneck edge weight. [1] For a directed graph, a similar problem is known as Minimum Bottleneck Spanning Arborescence (MBSA).
In an undirected graph G(V, E) and a function w : E → R, let S be the set of all spanning trees Ti. Let B(Ti) be the maximum weight edge for any spanning tree Ti. We define subset of minimum bottleneck spanning trees S′ such that for every Tj ∈ S′ and Tk ∈ S we have B(Tj) ≤ B(Tk) for all i and k. [2]
The graph on the right is an example of MBST, the red edges in the graph form a MBST of G(V, E).
An arborescence of graph G is a directed tree of G which contains a directed path from a specified node L to each node of a subset V′ of V \{L}. Node L is called the root of arborescence. An arborescence is a spanning arborescence if V′ = V \{L}. MBST in this case is a spanning arborescence with the minimum bottleneck edge. An MBST in this case is called a Minimum Bottleneck Spanning Arborescence (MBSA).
The graph on the right is an example of MBSA, the red edges in the graph form a MBSA of G(V, E).
A MST (or minimum spanning tree) is necessarily a MBST, but a MBST is not necessarily a MST. [3]
Camerini proposed [5] an algorithm used to obtain a minimum bottleneck spanning tree (MBST) in a given undirected, connected, edge-weighted graph in 1978. It half divides edges into two sets. The weights of edges in one set are no more than that in the other. If a spanning tree exists in subgraph composed solely with edges in smaller edges set, it then computes a MBST in the subgraph, a MBST of the subgraph is exactly a MBST of the original graph. If a spanning tree does not exist, it combines each disconnected component into a new super vertex, then computes a MBST in the graph formed by these super vertices and edges in the larger edges set. A forest in each disconnected component is part of a MBST in original graph. Repeat this process until two (super) vertices are left in the graph and a single edge with smallest weight between them is to be added. A MBST is found consisting of all the edges found in previous steps. [4]
The procedure has two input parameters. G is a graph, w is a weights array of all edges in the graph G. [6]
1 function MBST(graph G, weights w) 2 E ← the set of edges of G 3 if | E | = 1 thenreturnEelse 4 A ← half edges in E whose weights are no less than the median weight 5 B ← E - A 6 F ← forest of GB 7 ifF is a spanning tree then 8 return MBST(GB,w) 9 else 10 return MBST((GA)η, w) F
In the above (GA)η is the subgraph composed of super vertices (by regarding vertices in a disconnected component as one) and edges in A.
The algorithm is running in O (E) time, where E is the number of edges. This bound is achieved as follows:
In the following example green edges are used to form a MBST and dashed red areas indicate super vertices formed during the algorithm steps.
There are two algorithms available for directed graph: Camerini's algorithm for finding MBSA and another from Gabow and Tarjan. [4]
For a directed graph, Camerini's algorithm focuses on finding the set of edges that would have its maximum cost as the bottleneck cost of the MBSA. This is done by partitioning the set of edges E into two sets A and B and maintaining the set T that is the set in which it is known that GT does not have a spanning arborescence, increasing T by B whenever the maximal arborescence of G(B ∪ T) is not a spanning arborescence of G, otherwise we decrease E by A. The total time complexity is O(E log E). [5] [4]
function MBSA(G, w, T) isE ← the set of edges of Gif | E − T | > 1 thenA ← UH(E-T) B ← (E − T) − AF ← BUSH(GBUT) ifF is a spanning arborescence of G then S ← F MBSA((GBUT), w, T) else MBSA(G, w, TUB);
Gabow and Tarjan provided a modification of Dijkstra's algorithm for single-source shortest path that produces an MBSA. Their algorithm runs in O(E + V log V) time if Fibonacci heap used. [7]
For a graph G(V,E), F is a collection of vertices in V. Initially, F = s where s is the starting point of the graph G and c(s) = ∞ 1 function MBSA-GT(G, w, T) 2 Select v with minimum c(v) from F; 3 Delete it from the F; 4 for∀ edge(v, w) do 5 ifw∉F or ∉ Tree then 6 add w to F; 7 c(w) = c(v,w); 8 p(w) = v; 9 else 10 ifwF and c(w) > c(v, w)then 11 c(w) = c(v, w); 12 p(w) = v;
The following example shows that how the algorithm works.
Another approach proposed by Tarjan and Gabow with bound of O(E log* V) for sparse graphs, in which it is very similar to Camerini’s algorithm for MBSA, but rather than partitioning the set of edges into two sets per each iteration, K(i) was introduced in which i is the number of splits that has taken place or in other words the iteration number, and K(i) is an increasing function that denotes the number of partitioned sets that one should have per iteration. K(i) = 2k(i − 1) with k(1) = 2. The algorithm finds λ* in which it is the value of the bottleneck edge in any MBSA. After λ* is found any spanning arborescence in G(λ*) is an MBSA in which G(λ*) is the graph where all its edge's costs are ≤ λ*. [4] [7]
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.
In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.
Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest.
In computer science, Prim'salgorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph for which all edge weights are distinct, or a minimum spanning forest in the case of a graph that is not connected.
This is a glossary of graph theory terms. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.
In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.
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 of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . The size of an independent set is the number of vertices it contains. Independent sets have also been called internally stable sets.
In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time.
In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. A graph is said to be bridgeless or isthmus-free if it contains no bridges.
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.
In graph theory, a connected dominating set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph.
In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.
In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight . It is the directed analog of the minimum spanning tree problem. The algorithm was proposed independently first by Yoeng-Jin Chu and Tseng-Hong Liu (1965) and then by Jack Edmonds (1967).
In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.
In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of O(√n) vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most 2n/3 vertices.
In theoretical computer science and network routing, Suurballe's algorithm is an algorithm for finding two disjoint paths in a nonnegatively-weighted directed graph, so that both paths connect the same pair of vertices and have minimum total length. The algorithm was conceived by John W. Suurballe and published in 1974. The main idea of Suurballe's algorithm is to use Dijkstra's algorithm to find one path, to modify the weights of the graph edges, and then to run Dijkstra's algorithm a second time. The output of the algorithm is formed by combining these two paths, discarding edges that are traversed in opposite directions by the paths, and using the remaining edges to form the two paths to return as the output. The modification to the weights is similar to the weight modification in Johnson's algorithm, and preserves the non-negativity of the weights while allowing the second instance of Dijkstra's algorithm to find the correct second path.
In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the bottleneck shortest path problem or the maximum capacity path problem. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.
A randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices. It was developed by David Karger, Philip Klein, and Robert Tarjan. The algorithm relies on techniques from Borůvka's algorithm along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of divide and conquer algorithms, greedy algorithms, and randomized algorithms to achieve expected linear performance.