Udo Adamy7
, Christoph Ambuehl7
, R. Sai Anand8
and Thomas Erlebach8 
| (7) |
Institute for Theoretical Computer Science, ETH Zürich, 8092 Zürich, Switzerland |
| (8) |
Computer Engineering and Networks Laboratory, ETH Zürich, 8092 Zürich, Switzerland |
Abstract
The call control problem is an important optimization problem encountered in the design and operation of communication networks.
The goal of the call control problem in rings is to compute, for a given ring network with edge capacities and a set of paths
in the ring, a maximum cardinality subset of the paths such that no edge capacity is violated. We give a polynomial-time algorithm
to solve the problem optimally. The algorithm is based on a decision procedure that checks whether a solution with at least
k paths exists, which is in turn implemented by an iterative greedy approach operating in rounds. We show that the algorithm
can be implemented efficiently and, as a by-product, obtain a linear-time algorithm to solve the call control problem in chains
optimally.
Research partially supported by the Swiss National Science Foundation.
Supported by the joint Berlin/Zurich graduate program Combinatorics, Geometry, and Computation (CGC), financed by ETH Zurich
and the German Science Foundation (DFG).
References secured to subscribers.