Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Quasi-bipartite_graph> ?p ?o. }
Showing items 1 to 23 of
23
with 100 items per page.
- Quasi-bipartite_graph abstract "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 Zelikovskyproposed 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.".
- Quasi-bipartite_graph wikiPageID "11117830".
- Quasi-bipartite_graph wikiPageRevisionID "526553569".
- Quasi-bipartite_graph hasPhotoCollection Quasi-bipartite_graph.
- Quasi-bipartite_graph subject Category:Graph_families.
- Quasi-bipartite_graph type Abstraction100002137.
- Quasi-bipartite_graph type Family108078020.
- Quasi-bipartite_graph type GraphFamilies.
- Quasi-bipartite_graph type Group100031264.
- Quasi-bipartite_graph type Organization108008335.
- Quasi-bipartite_graph type SocialGroup107950920.
- Quasi-bipartite_graph type Unit108189659.
- Quasi-bipartite_graph type YagoLegalActor.
- Quasi-bipartite_graph type YagoLegalActorGeo.
- Quasi-bipartite_graph type YagoPermanentlyLocatedEntity.
- Quasi-bipartite_graph comment "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.".
- Quasi-bipartite_graph label "Quasi-bipartite graph".
- Quasi-bipartite_graph sameAs m.02r0lcb.
- Quasi-bipartite_graph sameAs Q7269439.
- Quasi-bipartite_graph sameAs Q7269439.
- Quasi-bipartite_graph sameAs Quasi-bipartite_graph.
- Quasi-bipartite_graph wasDerivedFrom Quasi-bipartite_graph?oldid=526553569.
- Quasi-bipartite_graph isPrimaryTopicOf Quasi-bipartite_graph.