Az optikai hálózatok kapcsán számos, a gráfok nyelvére lefordítható kérdés merül fel. Ilyen például a kapcsolatokat megvalósító utak kiválasztása és színezése. Az utak színezése a szokásos gráfszínezés problémának egy változata, így nem meglep?, hogy az útszínezési feladat teljes általánosságban NP-nehéz. Ezért a cél gyors de jól közelítõ eljárások keresése. Ebbõl a szempontból különbözõ speciális eseteket kellene megvizsgálni, hogy mely gráfosztályokra lehet jól közelít? algoritmust adni.

Az utak kiválasztásának módja kevésbé vizsgált, de legalább olyan érdekes része a problémának. Különösen az on-line változat, amikor menet közben egyenként érkeznek az újabb igények, melyeket a már meglev? kapcsolatok megzavarása nélkül kell kiszolgálni és mindezt úgy, hogy az összesen felhasznált színek száma ne legyen sokkal több az optimálisnál.

Irodalom:

Dr. Friedl Katalin
egyetemi docens
31-56
friedl@cs.bme.hu