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.
Famous quotes containing the word graph:
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)