Wiener Connector

Page history last edited by Dmitry Sokolov 7 years, 11 months ago

Go:

Visual Taxonomy

Links

Hide/Show:

https://en.wikipedia.org/wiki/Wiener_connector

In mathematics applied to the study of networks, the Wiener connector, named in honor of chemist Harry Wiener who first introduced the Wiener Index, 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.^[1]^[2]