Wyniki wyszukiwania - BazTech

1

Wykorzystanie algorytmów kolorowania grafu w sprzętowej realizacji systemu wnioskowania przybliżonego HFIS

Wyrwol B.

Przegląd Elektrotechniczny

|

2011

|

R. 87, nr 10

64-67

PL

Realizacja sprzętowego systemu wnioskowania przybliżonego, przy wykorzystaniu techniki dekompozycji opartej na operacjach projekcji oraz podziału, wymaga mniejszych nakładów sprzętowych i obliczeniowych. W artykule omówiono metodę podziału bazy wiedzy opartą na algorytmie kolorowania grafu, pokazano zależność uzyskiwanych wyników od sposobu uporządkowania reguł oraz przedstawiono szacunkowy koszt praktycznej implementacji modułu GCM, wspomagającego dekompozycję, w sprzętowym systemie FPGA-FIS.

EN

Hardware costs and computing time of the hardware implementation of the fuzzy inference system can be decreased using decomposition technique based on projection and partitioning. The paper presents the partitioning method of the knowledge base using graph vertex coloring algorithms. It discusses finally obtained results dependent on rule (graph vertex) arrangement and hardware cost estimation of the implementation the GCM module in the FPGA-FIS fuzzy inference system.

2

Metaheurystyka pszczela w kolorowaniu wierzchołków grafu

Rojek Ł., Wala K.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2011

|

T. 15, z. 2

421-428

PL

Metaheurystyka pszczela jest jedną z ostatnio wprowadzonych procedur rojowych. Symuluje ona inteligentne zachowanie roju żerujących pszczół miodnych. W pracy zastosowano metaheurystykę pszczelą do opracowania populacyjnego algorytmu optymalizacji problemów permutacyjnych. Zaprezentowano wyniki numeryczne testowania algorytmu w optymalizacji wierzchołkowego kolorowania grafu prostego.

EN

Bees metaheuristic is one of the most recently introduce swarm-based procedure. It simulates the intelligent foraging behavior of a honey bee swarm. In this work, the bees metaheuristic is used for work out some population-based algorithm for permutation optimization problems. A numerical test results obtained for optimizing vertex graph coloring problem are presented.

3

Sprzętowa implementacja zachłannego algorytmu kolorowania grafu

Wyrwoł B.

Elektronika : konstrukcje, technologie, zastosowania

|

2010

|

Vol. 51, nr 9

21-23

PL

Kolorowanie grafów znajduje zastosowanie wszędzie tam, gdzie konieczny jest podział zbioru na rozłączne podzbiory wg określonego kryterium jakie spełniają lub nie elementy zbioru. Większość algorytmów kolorowania realizowana jest zwykle na drodze programowej. W sytuacji, kiedy dużą rolę odgrywają uwarunkowania czasowe, konieczna jest realizacja sprzętowa z wykorzystaniem dedykowanego układu. W artykule przedstawiony został zachłanny algorytm kolorowania wierzchołków grafu oraz jego sprzętowa implementacja w układzie programowalnym FPGA. Dodatkowo omówiona została metoda reprezentacji danych opisujących strukturę grafu i przykład wykorzystania sprzętowego modułu kolorowania grafu, wspomagającego proces dekompozycji lingwistycznej, w systemie wnioskowania przybliżonego.

EN

Graph coloring algorithms are used wherever it is necessary to divide set on disjoint subsets according to specified criteria or not they meet the elements of the set. Most of the coloring algorithms are usually implemented as a computer or microcontroller program. To reduce computing time of the coloring result it is necessary to implement hardware using a dedicated chip. The paper presents graph greedy vertex algorithm and its hardware implementation in an FPGA chip. It describes also a graph data structure and finally implementation of the graph coloring module in the fuzzy hierarchical inference system. It is used in linguistic decomposition process of the knowledge base in the stage of the partitioning the rule base.

4

Nowe oszacowania górne dla liczby chromatycznej grafu i ich zastosowania algorytmiczne

Borowiecki P.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2007

|

T. 13

434-442

PL

Liczba chromatyczna grafu jest najmniejszą liczbą kolorów niezbędnych do pokolorowania jego wierzchołków w taki sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. W ogólnym przypadku problem wyznaczenia liczby chromatycznej grafu jest problemem NP-trudnym. W pracy tej wprowadzamy pojęcie funkcji potencjału określonej na wierzchołkach grafu i stosujemy ją w celu uzyskania nowych górnych oszacowań liczby chromatycznej. Porównujemy uzyskane oszacowania z ich klasycznymi odpowiednikami zależnymi od stopni wierzchołków. Wartości funkcji potencjału wykorzystujemy również do zdefiniowania nowych uporządkowań zbioru wierzchołków, co prowadzi do zdefiniowania dwóch nowych sekwencyjnych algorytmów kolorowania.

EN

Chromatic number of a graph is defined as the smallest number of colors required to color its vertices such that there does not exist a pair of adjacent vertices of the same color. In general it is NP-hard to determine the chromatic number of a graph. Within this paper we introduce the notion of a potential function of a graph defined on its vertex set and use it to establish new upper bounds on the chromatic number. The bounds are compared with their classical counterparts that use vertex degrees instead of potentials. Moreover, the values of a potential function are used to define new vertex orderings, what leads to new sequential graph coloring algorithms.