Quasi-bipartite graph

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. 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. [E.g., see Robins and Zelikovsky (2000), Gröpl et al. (2001), and Gröpl et al. (2002).] 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" "n2")", 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.

Notes

References

*cite conference
author = Gröpl, Clemens; Hougardy, Stefan; Nierhoff, Till; Prömel, Hans Jürgen
title = Lower Bounds for Approximation Algorithms for the Steiner Tree Problem
booktitle = Graph-Theoretic Concepts in Computer Science : 27th International Workshop, WG 2001
publisher = Springer-Verlag, Lecture Notes in Computer Science 2204
pages = 217
date = 2001
url = http://www.springerlink.com/content/pb68r0r25e97c3wq/

*cite journal
author = Gröpl, Clemens; Hougardy, Stefan; Nierhoff, Till; Prömel, 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

*cite conference
author = Rajagopalan, Sridhar; Vazirani, Vijay V.
title = On the bidirected cut relaxation for the metric Steiner tree problem
booktitle = Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms
date = 1999
pages = 742–751
url = http://portal.acm.org/citation.cfm?id=314909

*cite conference
author = Robins, Gabriel; Zelikovsky, Alexander
title = Improved Steiner tree approximation in graphs
booktitle = Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms
date = 2000
pages = 770–779
url = http://portal.acm.org/citation.cfm?id=338219.338638


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

  • Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

  • Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… …   Wikipedia

  • Vertex-transitive graph — In mathematics, a vertex transitive graph is a graph G such that, given any two vertices v1 and v2 of G , there is some automorphism : f : V(G) → V(G) such that : f (v1) = v2. In other words, a graph is vertex transitive if its automorphism group …   Wikipedia

  • List of mathematics articles (Q) — NOTOC Q Q analog Q analysis Q derivative Q difference polynomial Q exponential Q factor Q Pochhammer symbol Q Q plot Q statistic Q systems Q test Q theta function Q Vandermonde identity Q.E.D. QED project QR algorithm QR decomposition Quadratic… …   Wikipedia

  • Robertson–Seymour theorem — In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem[1]) states that the undirected graphs, partially ordered by the graph minor relationship, form a well quasi ordering.[2] Equivalently, every family of graphs that …   Wikipedia

  • Steiner tree problem — Steiner tree for three points A, B, and C (note there are no direct connections between A, B, C). The Steiner point S is located at the Fermat point of the triangle ABC …   Wikipedia

  • Jordan curve theorem — Illustration of the Jordan curve theorem. The Jordan curve (drawn in black) divides the plane into an inside region (light blue) and an outside region (pink). In topology, a Jordan curve is a non self intersecting continuous loop in the plane.… …   Wikipedia

  • Set cover problem — The set covering problem is a classical question in computer science and complexity theory. As input you are given several sets. They may have some elements in common. You must select a minimum number of these sets so that the sets you have… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”