PL
 |
EN
Ten serwis zostanie wyłączony 2025-02-11.
Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 10

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Modele i metody kolorowania grafów. Część I
100%
Kubale M.
|
|
tom R. 86, nr 9
115-117
PL
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.
EN
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.
2
Content available remote Modele i metody kolorowania grafów. Część II
100%
Kubale M.
Przegląd Elektrotechniczny
|
2012
|
tom R. 88, nr 11a
51-55
PL
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.
EN
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.
3
Content available remote A survey of hard-to-color graphs for off-line and on-line model of vertex coloring
63%
Borowiecki P. , Kubale M.
|
2001
|
tom 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.
4
Content available remote Scheduling unit execution time tasks with symmetric time-lags
63%
Janczewski R. , Kubale M.
|
2001
|
tom Vol. 9, nr 2
45-51
EN
In this paper we study the computational complexity of the problem of scheduling unit execution time tasks with symmetric time-lags. We discuss its applications and show that there is a direct relationship between solutions of the problem and T-colorings of the so-called graph of timing restrictions G. Next, we use this relation to study the computational complexity of our problem. We show that it is polynomial if G is a bipartite graph, pseudopolynomial if G is a graph with bounded cyclomatic number. and NP-hard in the strong sense if G is a complete graph.
5
Programowanie dynamiczne w rozw3iązywaniu problemów szeregowania zadań w systemach o acyklicznej strukturze
63%
Giaro K. , Kubale M.
|
2002
|
tom z. 134
173-184
PL
Rozważono rozrzedzone systemy niepodzielnych zadań dwuprocesorowych o jednostkowych długościach operacji oraz systemy maszyn dedykowanych (open shop, flow shop, mixed shop) o operacjach zero-jedynkowych. Przedstawiono rodzinę wielomianowych algorytmów opartych na programowaniu dynamicznym, pozwalających 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 acykliczne.
EN
We consider systems with nonpreemptable 2-processor tasks of unit execution times as well as systems of dedicated processors with zero-unit execution times. We are interested in systems whose scheduling graphs are acyclic. For such graphs we give a family of polynomial algorithms based on dynamic programming which yield optimal solutions with respect to a broad family of criterion functions.
6
Content available Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
63%
Furmańczyk H. , Kubale M.
|
2015
|
tom Vol. 25, no. 1
109--116
EN
In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP-complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize the makespan.
7
Content available Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
63%
Furmańczyk H. , Kubale M.
|
|
nr 1
8
Content available Model formalny dla problemu lokalizacji błędów w kodzie programu
63%
Dereniowski D. , Kubale M.
|
2007
|
tom 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.
9
Content available Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments
51%
Duraj S. , Kopeć P. , Kubale M. , Pikies T.
|
|
tom Vol. 11, no. 1-2
53--61
EN
In this paper, we consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that our problem can be solved to optimality in polynomial time under some restrictions imposed on the number of machines, their speeds, and the structure of the incompatibility graph. The theoretical considerations are accompanied by computer experiments with a certain model of scheduling.
10
Content available remote Some lower bounds on the Shannon capacity
51%
Jurkiewicz M. , Kubale M. , Turowski K.
Journal of Applied Computer Science
|
2014
|
tom Vol. 22, nr 2
31--42
EN
In the paper we present a measure of a discrete noisy channel, named the Shannon capacity, which is described in the language of graph theory. Unfortunately, the Shannon capacity C0 is difficult to calculate, so we try to estimate the value of C0 for specific classes of graphs, i.e. circular graphs.
first rewind previous Strona / 1 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ć.