35-489    Algorithmen für Kommunikationsnetze: Themenliste und Skript

Skript: vollständige Version (105 Seiten) als gzipped ps-file und als pdf-file

Voraussichtlich werden die folgenden Themen werden in der Vorlesung behandelt. Bei den meisten Themen sind auch Hinweise auf die Orginalliteratur angegeben, an der sich die Vorlesung orientiert.
  • Grundlagen (gzipped ps-Datei, pdf-Datei)
  • Minimale Spannbäume und Steiner-Bäume (gzipped ps-Datei, pdf-Datei)
  • Kürzeste Wege, Spanner und Netzwerkdesign (gzipped ps-Datei, pdf-Datei)
    S. Khuller, B. Raghavachari, N.E. Young: Balancing minimum spanning and shortest path trees. Algorithmica, Vol. 14, 1995, pp. 305-322.
    I. Althöfer, G. Das, D. Dobkin, D. Joseph: Generating sparse spanners for weighted graphs. In Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory (SWAT), 1990, pp. 26-37.
    B. Chandra, G. Das, G. Narasimhan, J. Soares: New sparseness results on graph spanners. In International Journal of Computational Geometry and Applications, 5(1-2):125-144, 1995.

    Y. Mansour, D. Peleg: An Approximation Algorithm for Minimum-Cost Network Design. Technical Report CS94-22, The Weizmann Institute of Science, October 1994.
    F.S. Salman, J. Cheriyan, R. Ravi, S. Subramanian: Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1997, pp. 619-628.
  • Datenstrukturen für IP Forwarding Tables (gzipped ps-Datei, pdf-Datei)
    Anhang mit Beispiel für dynamische Programmierung (gzipped ps-Datei, pdf-Datei)
    M. Waldvogel, G. Varghese, J. Turner, and B. Plattner: Scalable High Speed IP Routing Lookups. SIGCOMM'97, ACM Computer Communication Review, Volume 27, Number 4, October 1997, pp. 25-36. (ps-file)
    V. Srinivasan, G. Varghese: Fast Address Lookups Using Controlled Prefix Expansion. ACM Transactions on Computing Systems, Vol. 17, No. 1, February 1999, pp. 1-40.
    A. Feldmann, S. Muthukrishnan: Tradeoffs for Packet Classification. IEEE INFOCOM 2000. (gzip'ed postscript)
  • Online-Zugangskontrolle und Routing in ATM-Netzen (gzipped ps-Datei, pdf-Datei)

    S. Plotkin: Competitive Routing of Virtual Circuits in ATM Networks. IEEE Journal on Selected Areas in Communications, August 1995, pp. 1128-1136.
  • Wellenlängenzuteilung in optischen WDM-Netzen (gzipped ps-Datei, pdf-Datei)
    B. Beauquier, P. Hell, S. Perennes: Optimal wavelength-routed multicasting. Discrete Applied Mathematics, Vol. 84, 1998, pp. 15-20.
  • Ausfallsicherheit von Netzen (gzipped ps-Datei, pdf-Datei)
    R.E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1:146-160, 1972.
    K.P. Eswaran and R.E. Tarjan: Augmentation problems. In SIAM Journal on Computing, 5(4):653-665, 1976.
    Mechthild Stoer and Frank Wagner: A Simple Min-Cut Algorithm. Journal of the ACM, 44(4):585-591, 1997.



 
 
Back to TIK Homepage