✦ LIBER ✦

A note on optical routing on trees

✍ Scribed by S.Ravi Kumar; Rina Panigrahy; Alexander Russell; Ravi Sundaram

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 521 KB
Volume: 62
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00077-x

No coin nor oath required. For personal study only.

✦ Synopsis

Bandwidth is a very valuable resource in wavelength division multiplexed optical networks. The problem of finding an optimal assignment of wavelengths to requests is of fundamental importance in bandwidth utilization. We present a polynomial-time algorithm for this problem on fixed constant-size topologies. We combine this algorithm with ideas from Raghavan and Upfal (1994) to obtain an optimal assignment of wavelengths on constant degree undirected trees. Mihail, Kaklamanis, and Rao (1995) posed the following open question: what is the complexity of this problem on directed trees? We show that it is NP-complete both on binary and constant depth directed trees. @ 1997 Elsevier Science B.V.

📜 SIMILAR VOLUMES

On properties of multicast routing trees

✍ Milena Janic; Piet Van Mieghem 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB 👁 1 views

In the last several years we witnessed the proliferation of multimedia applications on the Internet. One of the unavoidable techniques to support this type of communication is multicasting. However, even a decade after its initial proposal, multicast is still not widely deployed. One of the reasons

Optimal wavelength routing on directed f

Optimal wavelength routing on directed fiber trees

✍ Thomas Erlebach; Klaus Jansen; Christos Kaklamanis; Milena Mihail; Pino Persiano 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 981 KB

We present a polynomial-time greedy algorithm that assigns proper wavelengths to a set of requests of maximum load L per directed fiber link on a directed fiber tree using at most 5/3L wavelengths. This improves previous results of Raghavan and Upfal (Proc.

A note on tree isomorphisms

✍ A.R Bednarek 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 139 KB

A note on bisecting minimum spanning tre

A note on bisecting minimum spanning trees

✍ W. M. Boyce; M. R. Garey; D. S. Johnson 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 281 KB

A note on finding shortest path trees

✍ Aaron Kershenbaum 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB 👁 1 views

A note on trees, tables, and algorithms

✍ Wayne Goddard; Stephen T. Hedetniemi 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB