In network theory, the Wiener connector is a means of maximizing efficiency in connecting specified "query vertices" in a network. Given a connected, undirected graph and a set of query vertices in a graph, the minimum Wiener connector is an induced subgraph that connects the query vertices and minimizes the sum of shortest path distances among all pairs of vertices in the subgraph. In combinatorial optimization, the minimum Wiener connector problem is the problem of finding the minimum Wiener connector. It can be thought of as a version of the classic Steiner tree problem (one of Karp's 21 NP-complete problems), where instead of minimizing the size of the tree, the objective is to minimize the distances in the subgraph.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Винеровский каркас (ru)
- Wiener connector (en)
|
| rdfs:comment
| - In network theory, the Wiener connector is a means of maximizing efficiency in connecting specified "query vertices" in a network. Given a connected, undirected graph and a set of query vertices in a graph, the minimum Wiener connector is an induced subgraph that connects the query vertices and minimizes the sum of shortest path distances among all pairs of vertices in the subgraph. In combinatorial optimization, the minimum Wiener connector problem is the problem of finding the minimum Wiener connector. It can be thought of as a version of the classic Steiner tree problem (one of Karp's 21 NP-complete problems), where instead of minimizing the size of the tree, the objective is to minimize the distances in the subgraph. (en)
- Винеровский каркас — средство максимизации эффективности соединений «выделенных вершин» в сети. Назван в честь химика (англ. Harry Wiener), предложившего индекс Винера. Если дан связный неориентированный граф и выделенный набор вершин в графе, минимальным каркасом Винера называется порождённый подграф, который соединяет выделенные вершины, минимизируя при этом сумму длин кратчайших путей среди всех пар вершин в подграфе. В комбинаторной оптимизации задача о минимальном винеровском каркасе — это задача поиска минимального винеровского каркаса. Задачу можно рассматривать как версию классической задачи Штейнера о минимальном дереве (одной из 21 NP-полных задач Карпа), где вместо минимизации размера дерева целью является минимизация расстояний в подграфе. (ru)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In network theory, the Wiener connector is a means of maximizing efficiency in connecting specified "query vertices" in a network. Given a connected, undirected graph and a set of query vertices in a graph, the minimum Wiener connector is an induced subgraph that connects the query vertices and minimizes the sum of shortest path distances among all pairs of vertices in the subgraph. In combinatorial optimization, the minimum Wiener connector problem is the problem of finding the minimum Wiener connector. It can be thought of as a version of the classic Steiner tree problem (one of Karp's 21 NP-complete problems), where instead of minimizing the size of the tree, the objective is to minimize the distances in the subgraph. The minimum Wiener connector was first presented by Ruchansky et al. in 2015. The minimum Wiener connector has applications in many domains where there is a graph structure and an interest in learning about connections between sets of individuals. For example, given a set of patients infected with a viral disease, which other patients should be checked to find the culprit? Or given a set of proteins of interest, which other proteins participate in pathways with them? The Wiener connector was named in honor of chemist Harry Wiener who first introduced the Wiener Index. (en)
- Винеровский каркас — средство максимизации эффективности соединений «выделенных вершин» в сети. Назван в честь химика (англ. Harry Wiener), предложившего индекс Винера. Если дан связный неориентированный граф и выделенный набор вершин в графе, минимальным каркасом Винера называется порождённый подграф, который соединяет выделенные вершины, минимизируя при этом сумму длин кратчайших путей среди всех пар вершин в подграфе. В комбинаторной оптимизации задача о минимальном винеровском каркасе — это задача поиска минимального винеровского каркаса. Задачу можно рассматривать как версию классической задачи Штейнера о минимальном дереве (одной из 21 NP-полных задач Карпа), где вместо минимизации размера дерева целью является минимизация расстояний в подграфе. Минимальный винеровский каркас впервые представили в 2015 году Ручански, Бончи и др. Минимальный винеровский каркас имеет приложения во многих областях, где имеется структура графа и целью изучения являются связи между набором индивидуальных элементов. Например, если есть набор пациентов, поражённых вирусной инфекцией, какие другие пациенты должны быть проверены, чтобы найти источник заражения? Или, если дан набор исследуемых протеинов, какие другие протеины участвуют в их путях взаимодействия? (ru)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)