| dbo: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. (en)
- Квазидвудольным называется случай задачи Штейнера о минимальном дереве (состоящей из неориентированного графа G и множества R терминальных вершин), в котором нетерминальные вершины графа G образуют независимое множество. Это определение обобщает концепцию двудольного графа — если граф G двудолен и одна из его долей образует множество R, то множество R автоматически является независимым. Данную концепцию предложили Раджагопалан и Вазирани и использовали её, чтобы дать -аппроксимационный алгоритм для задачи Штейнера в таких графах. Впоследствии Рицци избавился от в данной оценке, а Чакрабарти с соавторами предложили 4/3-аппроксимационный алгоритм. В дальнейшем ту же концепцию использовали другие авторы, например Робинс и Зеликовски предложили аппроксимационный алгоритм для задачи Штейнера, который на квазидвудольных графах имеет аппроксимационный коэффициент 1,28. Алгоритм Робинса и Зеликовски работает за время , где m и n — количества терминальных и нетерминальных вершин в графе соответственно. В дальнейшем, Грёпль с соавторами предложили 1,217-аппроксимационный алгоритм для особого случая однородных квазидвудольных случаев. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4009 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs: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. 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. (en)
- Квазидвудольным называется случай задачи Штейнера о минимальном дереве (состоящей из неориентированного графа G и множества R терминальных вершин), в котором нетерминальные вершины графа G образуют независимое множество. Это определение обобщает концепцию двудольного графа — если граф G двудолен и одна из его долей образует множество R, то множество R автоматически является независимым. (ru)
|
| rdfs:label
|
- Quasi-bipartite graph (en)
- Квазидвудольный граф (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
