Wyniki wyszukiwania - BazTech

1

The backbone coloring problem for small graphs

Janczewski R., Turowski K.

Journal of Applied Computer Science

|

2014

|

Vol. 22, nr 2

19--30

EN

In this paper we investigate the values of the backbone chromatic number, derived from a mathematical model for the problem of minimization of bandwidth in radio networks, for small connected graphs and connected backbones (up to 7 vertices). We study the relationship of this parameter with the structure of the graph and compare the results with the solutions obtained using the classical graph coloring algorithms (LF, IS), modified for the backbone coloring problem.

2

T-SL, T-LF i T-DSATUR - nowe heurystyki dla problemu przydziału częstotliwości

Janczewski R., Małafiejski M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

z. 136

97-105

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ł zawiera opis tego modelu, podstawowe informacje o jego złożoności obliczeniowej oraz opis trzech nowych heurystyk - algorytmów, które są bardzo efektywne, ale generują przybliżone rozwiązania problemu przydziału częstotliwości. Algorytmy te zostały zbadane zarówno metodami teoretycznymi - wskazano, dla jakich klas grafów interferencji zachowują się dobrze, a dla jakich źle, jak i doświadczalnymi - przytoczono wyniki testów, jakim zostały poddane na małych i średnich losowych grafach interferencji.

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 graph-theoretical model of FAP based on three notions: interference graphs, T-colorings and the T-span. We describe the model, provide basic information about its computational complexity and present three new heuristic approximate algorithms. Results of the theoretical analysis and computer tests of these algorithms are also included.

3

O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach

Giaro K., Janczewski R.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

z. 136

67-73

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.