 |
|
|||
| Authors: | Udo Adamy, Christoph Ambühl, Sai Anand, Thomas Erlebach |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | Call Control in Rings |
| Year: | 2002 |
| Month: | July |
| Pub-Key: | AAAE02 |
| Book Titel: | Lecture Notes in Computer Science. Proceedings of the 29th International Colloquium on Automata,Languages, and Programming (ICALP) |
| Volume: | 2380 |
| Pages: | 788-799 |
| Publisher: | Springer-Verlag |
| 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. |
| Location: | Malaga, Spain |
| Resources: | [BibTeX] |
