Quasi-bipartite graph

From Wikipedia, the free 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. This concept was introduced by Rajagopalan and Vazirani (1999), who used it to provide a (3/2 + ε) approximation algorithm for the Steiner tree problem on such instances. The same concept has been used by subsequent authors on the Steiner tree problem.^[1] Robins and Zelikovsky (2000), proposed an approximation algorithm for steiner tree problem on quasi-bipartite graphs and it has an approximation ratio 1.28. The complexity of Robins and Zelikovsky's algorithm is O(m n²), where m and n are the numbers of terminals and non-terminals in the graph, respectively. Furthermore, Gröpl et al. (2001) achieved an approximation ratio 1.217.

[edit] Notes

[edit] References

• Gröpl, Clemens; Hougardy, Stefan; Nierhoff, Till; Prömel, Hans Jürgen (2001). "Lower Bounds for Approximation Algorithms for the Steiner Tree Problem". Graph-Theoretic Concepts in Computer Science : 27th International Workshop, WG 2001: 217, Springer-Verlag, Lecture Notes in Computer Science 2204. 

• Gröpl, Clemens; Hougardy, Stefan; Nierhoff, Till; Prömel, Hans Jürgen (2002). "Steiner trees in uniformly quasi-bipartite graphs". Information Processing Letters 83 (4): 195–200. doi:10.1016/S0020-0190(01)00335-0. 

• Rajagopalan, Sridhar; Vazirani, Vijay V. (1999). "On the bidirected cut relaxation for the metric Steiner tree problem". Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms: 742–751. 

• Robins, Gabriel; Zelikovsky, Alexander (2000). "Improved Steiner tree approximation in graphs". Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms: 770–779.