Uogólnione algorytmy zachłanne w kontrastowym kolorowaniu grafów

• Autorzy: Janczewski R.

Warianty tytułu

EN

Generalized greedy algorithms and T-coloring of graphs

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2004
• Tom: T. 5
• Strony: 743--746
• Opis fizyczny: Bibliogr. 6 poz., 3 tab.

Twórcy

autor

Janczewski R.

• 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.