Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Call Control in Rings

Udo AdamyContact Information, Christoph AmbuehlContact Information, R. Sai AnandContact Information and Thomas ErlebachContact Information

(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).

Contact Information Udo Adamy
Email: adamy@inf.ethz.ch

Contact Information Christoph Ambuehl
Email: ambuehl@inf.ethz.ch

Contact Information R. Sai Anand
Email: anand@tik.ee.ethz.ch

Contact Information Thomas Erlebach
Email: erlebach@tik.ee.ethz.ch
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb01
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)