Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 1

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  k-drzewa
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
PL
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.
EN
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.
first rewind previous Strona / 1 next fast forward last
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ć.