In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, the minimum routing cost spanning tree of a
weighted graph
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* ...
is a
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...
minimizing the sum of pairwise distances between vertices in the tree. It is also called the optimum distance spanning tree, shortest total path length spanning tree, minimum total distance spanning tree, or minimum average distance spanning tree. In an unweighted graph, this is the spanning tree of minimum
Wiener index
In chemical graph theory, the Wiener index (also Wiener number) introduced by Harry Wiener, is a topological index of a molecule, defined as the sum of the lengths of the shortest paths between all pairs of vertices in the chemical graph representi ...
.
writes that the problem of constructing these trees was proposed by Francesco Maffioli.
It is
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
to construct it, even for unweighted graphs. However, it has a
polynomial-time approximation scheme
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
A PTAS is an algorithm which takes an in ...
. The approximation works by choosing a number
that depends on the approximation ratio but not on the number of vertices of the input graph, and by searching among all trees with
internal nodes.
The minimum routing cost spanning tree of an unweighted
interval graph
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line,
with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.
...
can be constructed in linear time. A polynomial time algorithm is also known for
distance-hereditary graph
In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any ...
s, weighted so that the weighted distances are hereditary.
Fairness considerations
Several works assume that different people may have different preferences on edges in the graph, and the goal is to find a spanning tree that is "socially" best.
* Darmann, Klamler and Pferschy present a
greedy algorithm
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locall ...
that finds such a spanning tree.
* Escoffier, Gourvès and Monnot study the problem under the
egalitarian rule In social choice and operations research, the egalitarian rule (also called the max-min rule or the Rawlsian rule) is a rule saying that, among all possible alternatives, society should pick the alternative which maximizes the ''minimum utility'' of ...
- maximizing the smallest utility of an agent.
* Galand, Perny and Spanjaard study the problem under the criterion of minimizing the
Choquet integral A Choquet integral is a subadditive or superadditive integral created by the French mathematician Gustave Choquet in 1953. It was initially used in statistical mechanics and potential theory, but found its way into decision theory in the 1980s, wh ...
.
See also
*
Optimal network design
Optimal network design is a problem in combinatorial optimization. It is an abstract representation of the problem faced by states and municipalities when they plan their road network. Given a set of locations to connect by roads, the objective is ...
- the problem of finding a spanning set (not necessarily a tree) that minimizes the sum of shortest path lengths.
References
Spanning tree
NP-complete problems
{{algorithm-stub