AN ENUMERATIVE ALGORITHM FOR THE MINIMUM WEIGHT t-SPANNER TREE PROBLEM

In the Minimum Weight $t$-Spanner Tree Problem, whose input is a triplet $(G,w,t)$, where $G=(V,E)$ is a simple graph, $w:E\rightarrow\mathbb{R}^{+}$ is an edge weighting function and $t\geq 1$ is a parameter, called the dilatation factor, the objective consists in determining a spanning tree $T$ of $G$ of minimum weight among those where the path between each pair of vertices $i$ and $j$ in tree $T$ has weight at most $t$ times the minimum weight of a path between $i$ and $j$ in $G$. It is known that determining a Minimum Weight $t$-Spanner Tree is an NP-hard problem even on the unit costs case. In this work, we propose an enumerative algorithm to solve this problem. It is the first one that does not depend on solving mathematical programs. We implemented the algorithm and compared the computational performance with the most efficient formulation from the literature.