Operations Research Seminar - 28/5/2014

Wednesday, 28 May 2014, 2:30 p.m.

Lecturer: Marta Pascoal (Instituto de Engenharia de Sistemas e Computadores de Coimbra – INESCC / Universidade de Coimbra)

Title: "Computing pairs of disjoint paths by order of cost"

Local: Room 1.3, Edifício VII
Faculdade de Ciências e Tecnologia, Quinta da Torre, Caparica

Abstract: A network consists of a graph structure, the arcs or nodes of which are valued. Such type of structure is used in many different applications, in particular it is often used to represent practical situations related with telecommunications or transportation which involve routing.

A path between two fixed nodes of a network can represent a route, along which data, goods or persons can be sent. Two paths between the same pair of nodes are said to be disjoint (or node disjoint) if they do not have nodes in common, besides the first and the last. Pairs of disjoint paths also have important applications in routing, for instance whenever a backup path is needed in case one of the arcs of the best path fails, or in order to avoid over-exposure of the same region to hazardous materials.

The problem of finding the minimum cost pair of disjoint paths can be formulated as a minimum cost flow problem and can be solved polynomially by an adaptation of labeling algorithms. In this seminar, we address the problem of ranking pairs of disjoint paths by increasing order of cost. A polynomial time algorithm to rank these solutions is discussed.