Referat dotyczy zagadnienia ścieżkowego kolorowania grafu, które stanowi naturalny model dla problemu routingu i przydziału częstotliwości w czysto optycznej sieci światłowodowej. Opisano podstawowe zasady i właściwości ścieżkowego kolorowania grafów. Zaprezentowano wybrane twierdzenia, oparte w dużej mierze na wynikach badań własnych. Omówiono złożoność obliczeniową problemu routingu chromatycznego i kolorowania ścieżek zarówno w przypadku ogólnym, jak i dla wybranych klas grafów. Scharakteryzowano złożoność obliczeniową badanych problemów w przypadkach szczególnych, gdy ograniczony jest albo rząd grafu, albo ograniczona jest moc zbioru ścieżek.
Autorzy
Informacje dodatkowe
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Język
- polski
- Rok wydania
- 2004
Źródło danych: MOSTWiedzy.pl - publikacja "Wybrane własności problemu routingu oraz kolorowania ścieżek w grafie." link otwiera się w nowej karcie
