Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
On the frequency assignment problem, T-colorings of graphs and partial k-trees
Konferencja
XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
Języki publikacji
Abstrakty
Problem przydziału częstotliwości to zagadnienie, które formułuje się zazwyczaj 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 i aby szerokość wykorzystanego przez nie pasma częstotliwości była minimalna. Zagadnienie to modeluje się zazwyczaj na gruncie teorii grafów za pomocą trzech pojęć: grafów interferencji, kontrastowych pokolorowań i T-rozpiętości. Niniejszy artykuł poświęcony jest złożoności obliczeniowej tego modelu; zawiera jego dokładny opis, dowód tego, że wyznaczanie T-rozpiętości i optymalnych pokolorowań kontrastowych jest NP-trudne nawet dla grafów dwudzielnych oraz wielomianowy algorytm wyznaczający optymalne pokolorowania kontrastowe dla tzw. częściowych k-drzew.
Frequency assignment problem (FAP) can be formulated as follows: there is a group of 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 and the span of used frequency band is minimal. The paper is devoted to the computational complexity of the graph-theoretical model of FAP based on three notions: interference graphs, T-colorings and the T-span. We describe the model, prove that the problem of computing the T-span is NP-hard even for bipartite graphs and present a polynomial time algorithm for finding optimal T-coloring for the socalled partial k-trees.
Słowa kluczowe
Rocznik
Tom
Strony
67--73
Opis fizyczny
Bibliogr. 6 poz.
Twórcy
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL6-0008-0037
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.