 |
|
|||
| Authors: | Thomas Erlebach, Danica Vukadinovic-Greetham |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | New results for path problems in generalized stars, complete graphs, and brick wall graphs |
| Year: | 2001 |
| Month: | August |
| Pub-Key: | EV01 |
| Book Titel: | Lecture Notes in Computer Science. Proceedings of the 13th International Symposium on Fundamentals of Computation Theory (FCT 2001) |
| Volume: | 2138 |
| Pages: | 483-494 |
| Publisher: | Springer-Verlag |
| Abstract: | Path problems such as the maximum edge-disjoint paths problem, the path coloring problem, and the maximum path coloring problem are relevant for resource allocation in communication networks, in particular all-optical networks. In this paper, it is shown that maximum path coloring can be solved optimally in polynomial time for bidirected generalized stars, even in the weighted case. Furthermore, the maximum edge-disjoint paths problem is proved NP-hard for complete graphs (undirected or bidirected), and a constant-factor approximation algorithm is presented. Finally, an open problem concerning the existence of routings that simultaneously minimize the maximum load and the number of colors is solved: an example for a graph and a set of requests is given such that any routing that minimizes the maximum load requires strictly more colors for path coloring than a routing that minimizes the number of colors. |
| Remarks: | 1st International Workshop on Efficient Algorithms |
| Location: | Riga, Latvia |
| Resources: | [BibTeX] |
