Vertex routing problems

Spanning tree methods

A tree is a connected, cycle free graph. A tree subgraph which meets all graph nodes is called a spanning tree. One say, a tree is rooted at the node r if for every node v, the tree path connecting r and v is non-blocking. A tree rooted at node r is sometimes called an r-arborescence.

Trees might be represented by either the predecessor labels, the subgraph multiplicities or the edge colours. Generally, the predecessor label representation is used. Only the Kruskal method differs: At an intermediate step of adding a tree edge, it does not know the arc orientation in the final rooted tree. The subgraph representation is used instead of the edge colours since sparse subgraphs of complete graphs are represented more economically.

The travelling salesman solver uses the concept of a one-cycle tree exposing an (arbitrary but fixed) node r: This denotes a spanning tree of the nodes other than r, adding the two minimum length edges incident with r. That yields a cycle through r and, when this cycle is contracted to a single node, a spanning tree rooted at the artificial node. Minimum one-cycle trees constitute lower bounds on the length of a Hamiltonian cycle.

The following shows a set of nodes in the Euclidian plane, a minimum one cycle tree exposing the upper left node, and a minimum spanning tree rooted at the same node:


[See API]

Steiner trees

The discrete Steiner tree problem is defined on (potentially sparse) graphs and distinguishs between terminal and Steiner graph nodes. In that setting, a Steiner tree denotes a tree or arborescence which is rooted at some terminal node and which spans all other terminal nodes. The Steiner nodes are spanned only if they form shortcuts between terminal nodes.

[See API]

Travelling salesman

A Hamiltonian cycle (or simply a tour) is a cycle which meets every graph node exactly once. The travelling salesman problem asks for a Hamiltonian cycle of minimum length.

As computing an optimal tour is NP-hard, the library includes construction heuristics, methods to compute lower bounds on the minimum tour length, and a branch & bound scheme.

In the following example, a graph, the length labels and an acoording minimum length tour are shown. The optimality can be concluded from the fact that this tour is also a minimum reduced length one-cycle tree (for the upper left node). The reduced length labels and the node potentials applied for length reduction are also displayed:


[See API]

Return to main page