“Quasi-bipartite graph”的意思、由来-开放百科全书

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 ^[1] 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^[2] and a 4/3 approximation algorithm was obtained by Chakrabarty et al.^[3]

The same concept has been used by subsequent authors on the Steiner tree problem, e.g.^[4] Robins and Zelikovsky^[5]

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 n²), where m and n are the numbers of terminals and non-terminals in the graph, respectively. Furthermore, Gröpl et al.^[6] gave a 1.217-approximation algorithm for the special case of uniformly quasi-bipartite instances.

References

1. ^{{citation | last1 = Rajagopalan | first1= Sridhar|last2= Vazirani|first2= Vijay V.|author2-link=Vijay Vazirani | contribution = On the bidirected cut relaxation for the metric Steiner tree problem | title = Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms | year = 1999 | pages = 742–751 | url = http://portal.acm.org/citation.cfm?id=314909}}.
2. ^{{citation |first = Romeo |last=Rizzi |title = On Rajagopalan and Vazirani's 3/2-approximation bound for the Iterated 1-Steiner heuristic |journal = Inf. Process. Lett. |volume = 86 |year = 2003 |pages = 335–338 |doi = 10.1016/S0020-0190(03)00210-2 |issue = 6}}.
3. ^{{citation | first1 = Deeparnab|last1= Chakrabarty |first2= Nikhil R. |last2=Devanur|first3= Vijay V.|last3=Vazirani|author3-link=Vijay Vazirani | contribution = New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem | title = Proc. 13th IPCO | year = 2008 | pages = 344–358 | doi = 10.1007/978-3-540-68891-4_24 | volume = 5035 | series = Lecture Notes in Computer Science | isbn = 978-3-540-68886-0}}.
4. ^{{citation | last1 = Gröpl|first1= Clemens|last2= Hougardy|first2= Stefan|last3= Nierhoff|first3= Till|last4= Prömel|first4= Hans Jürgen | contribution = Lower Bounds for Approximation Algorithms for the Steiner Tree Problem | title = Graph-Theoretic Concepts in Computer Science : 27th International Workshop, WG 2001 | publisher = Springer-Verlag, Lecture Notes in Computer Science 2204 | pages = 217–228 | year = 2001 | doi = 10.1007/3-540-45477-2_20 | volume = 2204 | series = Lecture Notes in Computer Science | isbn = 978-3-540-42707-0}}.
5. ^{{citation | last1 = Robins|first1= Gabriel|last2= Zelikovsky|first2= Alexander | contribution = Improved Steiner tree approximation in graphs | title = Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms | year = 2000 | pages = 770–779 | url = http://portal.acm.org/citation.cfm?id=338219.338638}}.
6. ^{{citation | last1 = Gröpl|first1= Clemens|last2= Hougardy|first2= Stefan|last3= Nierhoff|first3= Till| last4=Prömel|first4= Hans Jürgen | title = Steiner trees in uniformly quasi-bipartite graphs | journal = Information Processing Letters | volume = 83 | issue = 4 | year = 2002 | pages = 195–200 | doi = 10.1016/S0020-0190(01)00335-0}}.