Minimum Wiener Connector Problem

Given a connected graph $G = (V, E)$ and a set $Q \subseteq V$ of query vertices, find a subgraph of $G$ that connects all query vertices and has minimum Wiener index.

Parameters

$n$ : number of vertices
$m$ : number of edges
$q$ : number of query vertices

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 2 of 2 algorithms

				See more
Ruchansky	2015	$O(q(m \log(n)+n \log^2(n)))$	$O(q(m+n \log n))$
Exhaustive search	2015	2^(O(n))	O(n) auxiliary

Reductions Table

Insuffient Data to display table

Other relevant algorithms