## Contributed Session Thu.2.H 3503

#### Thursday, 13:15 - 14:45 h, Room: H 3503

**Cluster 23: Telecommunications & networks** [...]

### Paths, trees and flows

**Chair: Álvaro Junio Pereira Franco**

**Thursday, 13:15 - 13:40 h, Room: H 3503, Talk 1**

**Álvaro Junio Pereira Franco**

A new linear time algorithm to construct dominator trees of reducible flow graphs

**Coauthor: Carlos Eduardo Ferreira**

**Abstract:**

A flow graph *G = (V, E, r)* is a directed graph, where *r* is a vertex in *G* that reaches any vertex *v* in *G*. A vertex *w* dominates vertex *v* if any path from *r* to *v* passes through *w*. A vertex *w* is the immediate dominator of *v* (*\mathrm{id}(v) = w*) if *w* dominates *v* and any dominator of *v* dominates *w*. It is well known that for each vertex *v ≠ r* there is a single vertex *w* that dominates immediately *v*. The graph *T = (V, E*^{\}prime), where *E*^{\}prime = {(\mathrm{id}(v),v):v ∈ V\{r}} is a rooted tree (root in *r*) called dominator tree of *G*. Sophisticated algorithms have been proposed to construct a dominator tree of a flow graph (e.g., Georgiadis and Tarjan, 2004). Even if the flow graph is reducible the algorithms existing are hard to implement (e.g., the linear implementation of Ramalingam and Reps algorithm, 1994). We develop a linear time algorithm to construct a dominator tree of *G* (reducible). It uses simpler data structures to determine whether there are internally vertex-disjoint paths from *r* to *u* and from *r* to *v*, for all pairs of vertices *u, v* in *G*, and to answer lowest common ancestor queries in a depth-first spanning tree of *G*.

**Thursday, 13:45 - 14:10 h, Room: H 3503, Talk 2**

**Elena Fernandez**

A compact formulation for the optimum communication spanning tree problem

**Coauthors: Carlos Luna Mota, Gerhard Reinelt**

**Abstract:**

The optimum communication spanning tree problem (OCSTP) is a difficult combinatorial optimization problem with multiple applications in telecommunications and transportation. In the OCSTP communication requirements *r*_{ij} exist between pairs of nodes, and the communication cost between *i*, *j*, over a given spanning tree *T*, depends on *r*_{ij} and on the distance on *T* between *i* and *j*. Looking for a balance between construction and communication costs, the objective in the OCST is to find a spanning tree of minimum total communication cost. We present a formulation with two index decision variables, which models any partial order as a rooted tree. We further specialize the above formulation to model the OCSTP, by incorporating additional decision variables to represent the distance on the tree between pairs of nodes. We discuss some properties and reinforcements of the formulation, which is compared with a classical formulation with four index variables. Some numerical computational results are presented and analyzed.

**Thursday, 14:15 - 14:40 h, Room: H 3503, Talk 3**

**Per Olov Lindberg**

Updating shortest path subproblem solutions in large scale optimization

**Coauthor: Johan Holmgren**

**Abstract:**

In many large scale optimization applications, one repetitively solves shortest path (SP) subproblems, with slowly varying and possibly converging characteristics. In such situations, it’s worthwhile to update the subproblem solutions, rather than solving from scratch.

In this paper we describe simplex-like updating of the SP trees, using thread labels.

We suggest three improvements to the standard approach:

\begin{compactenum}[1.]

Thread following link scan,

bucketed link scan, and

acyclic thread

In thread following link scan, we only need a single traversal of the thread to find all entering links.

In the bucketed link scan, we do partial pricing. Instead of scanning all arcs, we keep and update a "bucket'' of "promising'' links. This gives suboptimal subproblem solutions, but speeds up the convergence. Every now and then, we do a complete scan, and then add and delete links to/from the buckets.

In acyclic thread, the thread is modified to scan an acyclic graph, i.e., the graph of bucket links. The acyclic thread scans the nodes in the graph-induced order, and does not need to be updated, unless new arcs are added.

We will present computational results for small to large scale traffic assignment problems.