PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 29

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  kolorowanie grafów
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available Better polynomial algorithms for scheduling unit-length jobswith bipartite incompatibility graphs on uniform machines
Pikies T., Kubale Marek
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2019
|
Vol. 67, nr 1
31--36
EN
The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|pj = 1, G = bisubquartic|Cmax. The second one is Algorithm 3 which is 4-approximate for the problem Qm|pj = 1, G = bisubquartic|ΣCj, where m ϵ {2, 3, 4}. The theory behind the proposed algorithms is based on the properties of 2-coloring with maximal coloring width, and on the properties of ideal machine, an abstract machine that we introduce in this paper.
2
Content available Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
Furmańczyk H., Kubale M.
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2017
|
Vol. 65, nr 1
29--34
EN
In the paper we consider the problem of scheduling n identical jobs on 4 uniform machines with speeds s1 ≥ s2 ≥ s3 ≥ s4, respectively. Our aim is to find a schedule with a minimum possible length. We assume that jobs are subject to some kind of mutual exclusion constraints modeled by a bipartite incompatibility graph of degree Δ, where two incompatible jobs cannot be processed on the same machine. We show that the general problem is NP-hard even if s1 = s2 = s3. If, however, Δ ≤ 4 and s1 ≥ 12s2, s2 = s3 = s4, then the problem can be solved to optimality in time O(n1.5). The same algorithm returns a solution of value at most 2 times optimal provided that s1 ≥ 2s2. Finally, we study the case s1 ≥ s2 ≥ s3 = s4 and give a 32/15-approximation algorithm running also in O(n1.5) time.
3
Content available remote 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.
4
Content available Minimization of bus stop number on a bus station
Palúch S.
Transport Problems
|
2013
|
T. 8, z. 1
113--118
EN
A bus station contains several bus stops. Only one bus can occupy a single bus stop at a time. Buses of many trips arrive to the bus station during the day (or during another considered period) and every bus occupies a bus stop for a certain time interval. The set of available bus stops is limited. This paper studies a problem how to assign a bus stop to every bus trip in order to minimize the number of assigned bus stops and in order to comply several additional conditions. Several approaches to this problem are presented. These approaches differ according to considered additional conditions.
PL
Na stacji autobusowej może znajdować się kilka platform. W tym samym czasie przy jednej platformie może znajdować się tylko jeden autobus. W ciągu dnia na stację autobusową przyjeżdżają autobusy z różnych połączeń i każdy z nich zajmuje platformę przez określony czas. Ten artykuł ma na celu pokazanie problemu przyporządkowania platform do wszystkich połączeń i jednoczesnej minimalizacji liczby platform przy spełnieniu określonych warunków. Prezentowane są różne sposoby rozwiązania problemu. Każdy ze sposobów różni się w zależności od dalszych warunków.
5
State minimization by means of incompatibility graph coloring
Czerwiński R., Kania D.
Elektronika : konstrukcje, technologie, zastosowania
|
2011
|
Vol. 52, nr 3
160-162
EN
A method for state minimization of FSMs is presented which is based on coloring the incompatibility graph, introduced in letter algorithm, it is very compact and can be implemented as a quick computer program, especially as a preprocessing method in the process of exact state minimization.
PL
Metoda minimalizacji stanów układów sekwencyjnych jest przedstawiona w artykule. Zaprezentowana metoda wykorzystująca metodę kolorowania grafu niezgodności stanów jest bardzo zwięzła i może być zaimplementowana jako szybki program komputerowy. Metoda jest szczególnie przydatna w procesie wstępnego zredukowania liczby stanów w celu przeprowadzenia dokładnej minimalizacji.
6
O złożoności problemów F-dekompozycji grafów>
Jesse-Józefczyk K.
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
|
2007
|
T. 13
419-426
PL
W pracy tej zostało przedstawionych kilka problemów związanych z F-dekompozycją grafów i jej złożonością obliczeniową. F-dekompozycję będziemy utożsamiać z częściowym dwukolorowaniem wierzchołków grafu. Kolorowanie to musi spełniać kilka warunków, z których najważniejszym jest to, aby krawędzie czerwono-niebieskie tworzyły zbiór rozspajający dany graf oraz wraz z wierzchołkami w tych kolorach nie indukowały pewnych grafów dwudzielnych.
EN
This paper presents selected problems concerning F-decomposition of graphs and its complexity. We identify the F-decomposition with a colouring of vertices of a graph. This colouring must satisfy several conditions and the most important of them is that the red-blue edges must be a cut-set of the given graph and together with the vertices coloured red and blue they cannot induce some bipartite graphs.
7
Content available Model formalny dla problemu lokalizacji błędów w kodzie programu
Dereniowski D., Kubale M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2007
|
T. 11, z. 1-2
81-88
PL
Istnieje szereg sposobów badania poprawności programów komputerowych. W artykule podejmujemy problem automatycznego testowania oprogramowania przy założeniu, że dany jest zbiór testów (asercji) dla poszczególnych fragmentów kodu. Dla uproszczenia analizy zakładamy, że badany fragment kodu zawiera dokładnie jeden błąd, co nie zmniejsza ogólności rozważań. W artykule analizujemy praktyczne aspekty powyższego problemu oraz rozważamy model teoretyczny oparty na teorii grafów, w szczególności jej chromatyczne aspekty oraz pewien model przeszukiwania grafu opisującego strukturę programu.
EN
There are several criteria for testing program correctness. In this paper we deal with the problem of automatic software testing under the assumption that the set of tests (assertions) is given for selected blocks of code. We simplify the analysis by assuming that the program being tested contains exactly one bug, but this does not lead to loss of generality. We consider some practical aspects of the above problem and a graph-theoretical model in general as well as some chromatic aspects of a graph searching model in particular.
8
Zastosowanie algorytmów rojowych do kolorowania grafów
Obszarski P., Piwakowski K.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
107-113
PL
Przedstawiamy sposób adaptacji heurystycznej metody przeszukiwania PSO (ang. Particle Swarm Optimization) do znajdowania suboptymalnych pokolorowań wierzchołkowych grafów prostych. Prezentujemy sposób przeprowadzenia eksperymentów obliczeniowych oraz ich wyniki.
EN
Adaptation of the Particle Swarm Optimization method for obtaining suboptimal vertex colorings of graphs is proposed. We present details of performed computational experiments and their results.
9
Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów
Kosowski A., Kuszner Ł.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
75-81
PL
W artykule podano algorytm rozproszonego, samostabilizującego się kolorowania grafów. Rozważamy spójny system niezależnych, asynchronicznych węzłów, z których każdy posiada tylko i wyłącznie lokalną wiedzę o systemie. Bez względu na stan początkowy system powinien osiągnąć pożądany stan globalny, wykonując w każdym z węzłów algorytm dany w postaci zbioru reguł. Zgodnie z naszą wiedzą przedstawiony algorytm jest pierwszym samostabilizującym algorytmem dokładnego kolorowania grafów dwudzielnych, działającym w wielomianowej liczbie ruchów.
EN
In the paper a distributed self-stabilizing algorithm for graph coloring is given. We consider a connected system of autonomous asynchronous nodes, each of which has only local information about the system. Regardless of the initial state, the system must achieve a desirable global state by executing a set of rules assigned to each node. Our method based on spanning trees is applied to give the first (to our knowledge) self-stabilizing algorithms working in a polynomial number of moves, which color bipartite graphs with exactly two colors.
10
Generowanie sąsiedztwa w algorytmach lokalnych poszukiwań uporządkowanego kolorowania grafów
Dereniowski D.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
51-56
PL
Przedstawienie rozwiązań problemów kombinatorycznych w postaci permutacji daje podstawy do konstrukcji algorytmów lokalnych poszukiwań. Uporządkowane pokolorowanie grafu można zapisać w postaci permutacji wierzchołków grafu. Podstawowe operacje, prowadzące do generowania sąsiedztwa rozwiązania, to zamiana dwóch elementów lub przesunięcie elementu permutacji. W artykule wskazujemy metodę, pozwalającą na wykonanie takich operacji w czasie O(m), przy założeniu, że dane jest drzewo eliminacji wyjściowej permutacji.
EN
Representing solutions to combinatorial problems as permutations allows us to use local search algorithms for solving them. A vertex ranking of a graph can be represented by a permutation of the vertices of the graph. Basic operations for generating a neighborhood of a current solution are swapping two elements of the permutation or changing a position of an element. We show how to perform such operations in time O(m) assuming that an elimination tree of the current permutation is given.
11
Efektywność algorytmów dynamicznego kolorowania grafów - zastosowania w sieciach optycznych WDM
Borowiecki P., Sidorowicz E.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 144
135-142
PL
W pracy tej formułujemy problem dynamicznego kolorowania grafów, analizujemy efektywność algorytmu zachłannego First-Fit (w skrócie FF) oraz wskazujemy na jego zastosowanie w problemie przydziału długości fali w sieciach optycznych WDM. W szczególności podajemy dolne i górne oszacowania dobroci algorytmu FF. Wskazujemy istnienie klas grafów G, dla których różnica pomiędzy wartością rozwiązania generowanego przez algorytm FF(G) a wartością optymalną OPT(G) może być dowolnie duża. Z drugiej strony dowodzimy, że dla dowolnego grafu G używanego przez nas w problemie przydziału długości fali zawsze zachodzi FF(G) < 20PT(G).
EN
Within this paper we introduce a problem of dynamie graph coloring and analyze effectiveness of greedy algorithm First-Fit (FF for short). We point out an important application of a new model to wavelength assignment problem in WDM networks. In particular, we give lower and upper bounds on the performance ratio of FF. We prove that for some classes of graphs G, the difference between the solution value FF(G) and optimum value OPT(G) may be arbitrarily large. On the other hand, for all graphs, that we used in the wavelength assignment problem FF(G) < 20PT(G) holds.
12
Content available Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesowych w oknach czasowych
Giaro K., Kubale M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2005
|
T. 9, z. 1-2
85-94
PL
W artykule rozważono rozrzedzone systemy niepodzielnych zadań 1- i 2-procesorowych o jednostkowych czasach wykonywania. Przedstawiono wielomianowe algorytmy wykorzystujące programowanie dynamiczne, pozwalające na znalezienie optymalnego uszeregowania względem szerokiej rodziny funkcji kryterialnych. Stopień rozrzedzenia systemu zdefiniowano, posługując się jego modelem grafowym - w zakresie naszego zainteresowania leżą jedynie takie instancje problemów szeregowania, których modelami są grafy o ograniczonej liczbie cyklomatycznej. Istotnym elementem opracowanych procedur są algorytmy rozwiązujące pewne zagadnienia związane z wyszukiwaniem skojarzeń w grafach.
EN
In the paper sparse systems of dedicated 1- and 2-processor tasks with unit execution times are considered. Polynomial-time algorithms based on dynamic programming are given. These algorithms allow finding optimal solutions with respect to broad range of criterion functions. The sparsity of a system is measured in terms of the number of edges in the corresponding scheduling graph. More precisely, we are focused on graphs whose cyclomatic number is bounded by a constant. Our algorithms invoke procedures for finding maximal matching in graphs.
13
Content available remote Ant algorithms for solution of graph related optimization problems
Walkowiak K.
Journal of Applied Computer Science
|
2003
|
Vol. 11, nr 2
83-97
EN
One of the most promising innovations in the area of heuristics is the development of evolutionary algorithms. A valuable and novel proposition in this area is ant algorithm. Researchers examining the behavior of real ants developed algorithms and applied them to various optimization problems. An important field of interest is graph related optimization problems, since ant algorithms can be easily mapped to such problems. In this paper we introduce elementary features of ant algorithms. We discuss recent research on ant algorithms concentrating on the graph coloring problem which is equivalent to the problem of map coloring. We also discuss recent work on ant algorithms in the field of computer networks. A new ant algorithm for design of static non-bifurcated multicommodity flows in computer networks is proposed.
14
Uporządkowane kolorowane wierzchołki grafów
Kubale M., Dereniowski D.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 136
121-131
PL
W pracy przedstawiamy stosunkowo nowy model kolorowania grafów, mianowicie kolorowanie uporządkowane. Po scharakteryzowaniu potencjalnych zastosowań tego modelu przedstawiamy liniowy algorytm kolorowania grafów w sposób przybliżony. Pokazujemy klasy grafów, które ten algorytm koloruje optymalnie i klasy grafów, dla których błąd pokolorowania może być dowolnie duży. Przedstawiamy również doświadczenia komputerowe zebrane w trakcie jego implementacji i testowania na grafach losowych.
EN
We present a relatively new model of graph coloring, namely ordered (rank) coloring. After characterizing potential applications of this model, we give a linear-time algorithm KU for approximate graph coloring. We show graph classes that our algorithm colors optimally and graph classes that can be colored arbitrarily bad. Finally, we give results of computational experiments gained while testing algorithm KU on random graphs.
15
Rozproszone kolorowanie grafów
Kuszner Ł.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 136
145-156
PL
W pracy zaprezentowano nowy rozproszony algorytm kolorowania grafów. Przeprowadzone eksperymenty pokazują, że daje on lepsze wyniki niż znany wcześniej algorytm trywialny.
EN
In the paper we present a new distributed algorithm for graph coloring. A practical simulation shows that the algorithm performs much better then a naive distributed algorithm.
16
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.
17
Efektywność algorytmów kolorowania grafów w trybie on-line (II)
Borowiecki P.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 136
11-20
PL
Z praktycznego punktu widzenia analiza najgorszego przypadku okazuje się często zbyt pesymistyczna, natomiast zachowanie algorytmu dla spotykanych w rzeczywistości danych jest najczęściej dużo lepsze niż dla stosunkowo nielicznych instancji, decydujących o złej efektywności w najgorszym przypadku. Wśród parametrów pozwalających na ocenę oczekiwanego zachowania algorytmu kolorowania w trybie on-line koncentrujemy się na podatności grafu. Definiujemy operację zachowującą podatność dla algorytmu First-Fit. Dla tego samego algorytmu rozstrzygamy również problem istnienia grafów o dowolnie małej podatności. Dla znanej z wielu zastosowań rodziny grafów przedziałów prezentowane są wnioski płynące z eksperymentalnego porównania efektywności dwóch znanych algorytmów kolorowania on-line.
EN
It usually happens that worst case analysis leads to the results which are too pessimistic to be valuable in real live applications. In this paper we investigate an expected effectiveness of on-line graph coloring algorithms, in particular the susceptibility of graphs to algorithm First-Fit is analyzed. The operation preserving susceptibilty is defined and an existence of graphs having arbitrarily low susceptibility to First-Fit, is proved. For well known and widely applicable family of interval graphs, the results of comparative experimental study of expected behavior for two on-line coloring algorithms are given.
18
Cyrkularny indeks chromatyczny grafów kubicznych
Nadolski A.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 136
157-166
PL
W referacie omówimy własności cyrkularnego kolorowania krawędzi grafów oraz cyrkularnego indeksu chromatycznego. Po zdefiniowaniu tego rodzaju kolorowania zbadamy, które ze znanych wyników dla klasycznego kolorowania krawędzi grafów kubicznych można przenieść na rozważany model kolorowania. Dodatkowo podamy nietrywialne oszacowanie na cyrkularny indeks chromatyczny dla nieskończonej rodziny grafów kubicznych klasy 2.
EN
In this contribution we consider the properties of circular edge coloring of a graph and the circular chromatic index. After giving a definition of this kind of graph coloring, we study, which of the known results for classical edge coloring for cubic graphs can be applied to the considered model of coloring. Moreover, we bound the circular chromatic index for an infinite family of Class 2 cubic graphs.
19
Algorytmy radiowego kolorowania grafów
Kubale M., Kosowski A.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 136
133-144
PL
W pracy opisane są podstawowe zasady i właściwości radiowego kolorowania grafów. Podane są oszacowania radiowej liczby chromatycznej grafu w przypadku ogólnym dla ścieżek i cykli oraz dokładne wartości radiowej liczby chromatycznej dla grafów pełnych k-dzielnych, kół i dwugwiazd. Zamieszczono także przykładowe wyniki porównania dobroci suboptymalnych, sekwencyjnych algorytmów radiokolorowania grafów.
EN
The basic principles and features of graph radiocoloring are presented in this paper. Lower and upper bounds for the radiochromatic number of graphs are given, in the general case as well as for paths and cycles. Exact values of the radiochromatic number are given for complete k-parite graphs, wheels and double stars. The paper also contains a comparison of the quality of suboptimal, sequential radiocoloring algorithms having polynomial-time complexity.
20
Content available remote A survey of hard-to-color graphs for off-line and on-line model of vertex coloring
Borowiecki P., Kubale M.
Journal of Applied Computer Science
|
2001
|
Vol. 9, nr 2
7-17
EN
In the paper we review the most popular on-line and off-line graph coloring algorithms. For each algorithm we give: short description. performance guarantee, the smallest HC and slightly HC graphs, positive cases and negative cases. Finally, we give the smallest benchmark for off-line sequential algorithms and the smallest weak benchmark for on-line algorithms.
first rewind previous Strona / 2 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ć.