Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Generalized greedy algorithms and T-coloring of graphs
Języki publikacji
Abstrakty
Kontrastowe kolorowanie grafów jest uogólnieniem wierzchołkowego kolorowania grafów znajdującym zastosowanie m.in. w problemie przydziału częstotliwości, zagadnieniu komiwojażera, układaniu rozkładów zajęć i szeregowaniu zadań. Niniejszy referat poświęcony jest uogólnionym algorytmom zachłannym, tj. algorytmom, które kolorują kontrastowo grafy w oparciu o reguły stanowiące uogólnienie reguły zachłannego kolorowania. Referat zawiera opis tych algorytmów, krótką analizę ich właściwości oraz wyniki eksperymentów komputerowych przeprowadzonych w celu sprawdzenia, o ile są te algorytmy lepsze od zachłannych.
The paper is devoted to the so-called generalized greedy algorithms and their application to T-coloring. T-coloring of graphs is a generalization of classical vertex coloring of graphs whose appplications include: frequency assignment problem, travelling salesman problem, timetabling and scheduling. The generalized greedy algorithms are briefly discussed and compared to the greedy algorithm.
Słowa kluczowe
Rocznik
Tom
Strony
743--746
Opis fizyczny
Bibliogr. 6 poz., 3 tab.
Twórcy
autor
- Katedra Algorytmów i Modelowania Systemów, Politechnika Gdańska
- Katedra Algorytmów i Modelowania Systemów, Politechnika Gdańska
Bibliografia
- [1] Hale W.K.: Frequency assignment: theory and applications, Proceedings of the IEEE 68 (1980), str. 1497-1514.
- [2] Janczewski R., Kubale M.: The T-DSATUR algorithm - an interesting generalization of the DSATUR algorithm, Advanced Computer Systems V, Szczecin 1998, str. 288-289.
- [3] Janczewski R.: Kontrastowe kolorowanie grafów i jego zastosowania, Rozprawa doktorska, 2001.
- [4] Janczewski R.: Divisibility and T-span of graphs, Discrete Mathematics 234 (2001), str. 171-179-
- [5] Janczewski R., Małafiejski M.: T-SL, T-SLF i T-DSATUR - nowe heurystyki dla problemu przydziału częstotliwości, Zeszyty Naukowe Politechniki Śląskiej, Seria Automatyka 136 (2002), str. 97-105.
- [6] Giaro K., Janczewski R., Małafiejski M.: The complexity of the T-coloring problem for graphs with small degree, Discrete Applied Mathematics 129 (2003), str. 361-369.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BPG5-0011-0094