Temat: coloring - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
Autorzy:: Furmańczyk, H.
Kubale, M.
Powiązania:: https://bibliotekanauki.pl/articles/230004.pdf
Data publikacji:: 2015
Wydawca:: Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:: batch scheduling
equitable coloring
semi-equitable coloring
cubic graph
Opis:: 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.
Źródło:: Archives of Control Sciences; 2015, 25, 1; 109-116
1230-2384
Pojawia się w:: Archives of Control Sciences
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
Autorzy:: Furmańczyk, H.
Jastrzębski, A.
Kubale, M.
Powiązania:: https://bibliotekanauki.pl/articles/230069.pdf
Data publikacji:: 2016
Wydawca:: Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:: computer experiments
corona graph
equitable chromatic number
equitable coloring conjectures
NP-hardness
polynomial heuristics
Opis:: In many applications in sequencing and scheduling it is desirable to have an underlaying graph as equitably colored as possible. In this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.
Źródło:: Archives of Control Sciences; 2016, 26, 3; 281-295
1230-2384
Pojawia się w:: Archives of Control Sciences
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
Autorzy:: Furmańczyk, H.
Kubale, M.
Powiązania:: https://bibliotekanauki.pl/articles/200295.pdf
Data publikacji:: 2017
Wydawca:: Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:: equitable coloring
NP-hardness
polynomial algorithm
scheduling
uniform machine
kolorowanie grafów
twardość NP
algorytm wielomianowy
planowanie
Opis:: 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.
Źródło:: Bulletin of the Polish Academy of Sciences. Technical Sciences; 2017, 65, 1; 29-34
0239-7528
Pojawia się w:: Bulletin of the Polish Academy of Sciences. Technical Sciences
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: The smallest hard-to-color graphs for the classical, total and strong colorings of vertices
Autorzy:: Kubale, M.
Manuszewski, K.
Powiązania:: https://bibliotekanauki.pl/articles/206254.pdf
Data publikacji:: 1999
Wydawca:: Polska Akademia Nauk. Instytut Badań Systemowych PAN
Tematy:: optymalizacja
teoria grafów
złożoność obliczeniowa
benchmark
chromatic number
chromatic sum
graph oring
hard-to-color graph
NP-completeness
strong coloring
Opis:: : Let A(G) be the number of colors used by algorithm to color the vertices of graph G. A graph G is said to be hard-to-color (HC) (resp. slightly HC) if for every (resp. some) implementation of the algorithm A we have A(G) > chi(G), where chi(G) is the chromatic number of G. The study of HC graphs makes it possible design improved algorithms trying to avoid hard instances as far possible. Hard-to-color graphs are also good benchmarks for the evaluation of existing and future algorithms and provide an alternative way of assessing their quality. In this paper we demonstrate the smallest HC graphs for the best known coloring heuristics in classical applications, as well as when adapted to the chromatic sum coloring and strong coloring of vertices.
Źródło:: Control and Cybernetics; 1999, 28, 2; 355-365
0324-8569
Pojawia się w:: Control and Cybernetics
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 5.

Tytuł:: Towards the boundary between easy and hard control problems in multicast Clos networks
Autorzy:: Obszarski, P.
Jastrzębski, A.
Kubale, M.
Powiązania:: https://bibliotekanauki.pl/articles/200819.pdf
Data publikacji:: 2015
Wydawca:: Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:: Clos-network
2-cast call
hypergraph edge coloring
rearrageable network
nonblocking network
NP-completeness
3-uniform hypergraph
sieci
połączenie sieciowe
problem sieciowy
Opis:: In this article we study 3-stage Clos networks with multicast calls in general and 2-cast calls, in particular. We investigate various sizes of input and output switches and discuss some routing problems involved in blocking states. To express our results in a formal way we introduce a model of hypergraph edge-coloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially solvable instances as well as a number of NP-complete cases. Our results warn of possible troubles arising in the control of Clos networks even if they are composed of small-size switches in outer stages. This is in sharp contrast to classical unicast Clos networks for which all the control problems are polynomially solvable.
Źródło:: Bulletin of the Polish Academy of Sciences. Technical Sciences; 2015, 63, 3; 739-744
0239-7528
Pojawia się w:: Bulletin of the Polish Academy of Sciences. Technical Sciences
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja