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