Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Przegląd Elektrotechniczny

2 Kubale M.

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: chromatic index

Sortuj według:

Ogranicz wyniki do:

Modele i metody kolorowania grafów. Część II

Kubale M.

Przegląd Elektrotechniczny

2012

R. 88, nr 11a

51-55

Niniejszy artykuł jest drugą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny) oraz podano potencjalne zastosowania rozważanych modeli w problemach naukowo-technicznych.

This is the second of a couple of review papers on models and methods of graph coloring. We present herein the main models of graph coloring from a practical point of view. In particular, we show various criteria and modifications of classical coloring model. Since graph coloring is NP-hard in various modifications and variants, we give simple bounds on the chromatic number (chromatic index) as well as we give potential applications of the chromatic methods in science and technology.

Modele i metody kolorowania grafów. Część I

Kubale M.

Przegląd Elektrotechniczny

2010

R. 86, nr 9

115-117

Niniejszy artykuł jest pierwszą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano: (1) co można kolorować w grafie (np. wierzchołki, krawędzie, końcówki, ściany, jednocześnie wierzchołki i krawędzie) oraz (2) jak można kolorować (np. dzielenie kolorów, zawijanie kolorów). Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podajemy oszacowania na liczbę chromatyczną (indeks chromatyczny) oraz podajemy potencjalne zastosowania rozważanych modeli w problemach naukowo-technicznych.

This is the first of a couple of review papers on models and methods of graph coloring. We present herein the main models of graph coloring from a practical point of view. In particular, we show: (1) what elements of a graph can be colored (e.g. vertices, edges, faces, incidences) and (2) how these elements can be colored (e.g. fractional coloring, circular coloring). Since graph coloring is NP-hard in various modifications and variants, we give simple bounds on the chromatic number (chromatic index) as well as we give potential applications of the chromatic methods in science and technology.