Quasi-bipartite graph
Encyclopedia
In the mathematical
field of graph theory
, an instance of the Steiner tree problem (consisting of an undirected graph G and a set R of terminal vertices that must be connected to each other) is said to be quasi-bipartite if the non-terminal vertices in G form an independent set
, i.e. if every edge is incident on at least one terminal. This generalizes the concept of a bipartite graph
: if G is bipartite, and R is the set of vertices on one side of the bipartition, the set to R is automatically independent.
This concept was introduced by Rajagopalan and Vazirani who used it to provide a (3/2 + ε) approximation algorithm
for the Steiner tree problem on such instances. Subsequently the ε factor was removed by Rizzi and a 4/3 approximation algorithm
was obtained by Chakrabarty et al.
The same concept has been used by subsequent authors on the Steiner tree problem, e.g.. Robins and Zelikovsky
proposed an approximation algorithm
for Steiner tree problem which on quasi-bipartite graphs has approximation ratio 1.28. The complexity of Robins and Zelikovsky's algorithm is O(m n2), where m and n are the numbers of terminals and non-terminals in the graph, respectively. Furthermore, Gröpl et al. gave a 1.217-approximation algorithm for the special case of uniformly quasi-bipartite instances.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, an instance of the Steiner tree problem (consisting of an undirected graph G and a set R of terminal vertices that must be connected to each other) is said to be quasi-bipartite if the non-terminal vertices in G form an independent set
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
, i.e. if every edge is incident on at least one terminal. This generalizes the concept of a bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
: if G is bipartite, and R is the set of vertices on one side of the bipartition, the set to R is automatically independent.
This concept was introduced by Rajagopalan and Vazirani who used it to provide a (3/2 + ε) approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
for the Steiner tree problem on such instances. Subsequently the ε factor was removed by Rizzi and a 4/3 approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
was obtained by Chakrabarty et al.
The same concept has been used by subsequent authors on the Steiner tree problem, e.g.. Robins and Zelikovsky
proposed an approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
for Steiner tree problem which on quasi-bipartite graphs has approximation ratio 1.28. The complexity of Robins and Zelikovsky's algorithm is O(m n2), where m and n are the numbers of terminals and non-terminals in the graph, respectively. Furthermore, Gröpl et al. gave a 1.217-approximation algorithm for the special case of uniformly quasi-bipartite instances.