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


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


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 rij exist between pairs of nodes, and the communication cost between i, j, over a given spanning tree T, depends on rij 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


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:

  • 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.


  •   Payday Loans California. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.