O złożoności problemu przydziału częstotliwości i kontrastowego kolorowania grafów

• Autorzy: Janczewski R.

Warianty tytułu

EN

On the complexity of frequency assignment problem and T-coloring of graphs

• Konferencja: Automatyzacja procesów dyskretnych/krajowa konferencja (XII ; 13-16.09.2000 ; Zakopane)
• Języki publikacji: PL

Abstrakty

PL

Tytułowy problem przydziału częstotliwości można opisać następująco: na pewnym obszarze znajduje się grupa nadajników radiowych, którym trzeba przydzielić częstotliwości w taki sposób, żeby nie zakłócały się podczas nadawania. Zagadnienie to można sprowadzić do wyszukiwania tzw. kontrastowych pokolorowań grafu interferencji. Celem niniejszej pracy jest przedstawienie bieżącego stanu wiedzy na temat złożoności zagadnienia polegającego na wyszukiwaniu kontrastowych pokolorowań optymalizujących pewne kryteria jakości, takie jak rozpiętość czy rozpiętość krawędziowa. Wyodrębnione zostaną znane przypadki wielomianowe (grafy dwudzielne, kaktusy, grafy zewnętrznie planarne) i NP-zupełne (grafy pełne, r-regularne dla r>4 i podkubiczne).

EN

The frequency assignment problem can be defined as follows: there are several transmitters situated in a certain region of a plane; a channel is to be assigned to each of them in such a way that there is no interference during transmitting. The problem can be represented as one of graph coloring problems. More precisely, it has been proved that to solve the problem it suffices to build the so-called interference graph and find one of its T-colorings. The aim of the paper is to present state-of-the-art on the complexity of the problem of finding T-colorings optimizing some criterions such as the span or edge span. We discuss known polynomial (bipartite graphs, cacti, outerplanar) and NP-complete (complete graphs, subcubic and r-regular for r>4) cases.

Słowa kluczowe

PL

problem przydziału częstotliwości; T-kolorowanie; T-rozpiętość; kolorowanie grafów

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2000
• Tom: z. 131
• Strony: 95--101
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Janczewski R.

• Katedra Podstaw Informatyki Politechnika Gdańska, 80-952 Gdańsk, ul. Narutowicza 11/12, tel. [phone]