Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "coloring" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 198
Tytuł:
Analysis of the efficiency of graph coloring algorithms
Autorzy:
Kubale, Marek
Powiązania:
https://bibliotekanauki.pl/articles/748571.pdf
Data publikacji:
1982
Wydawca:
Polskie Towarzystwo Matematyczne
Tematy:
Computational complexity and efficiency of algorithms
Coloring of graphs and hypergraphs
Graph theory
Opis:
.
This paper discusses the computational efficiency and the number of colors used by the following algorithms for coloring vertices of graphs: sequential coloring and sequential coloring with interchange algorithms for a largest-first and a smallest-last orderings of vertices, the coloring-pairs algorithm, and the approximately maximum independent set algorithm. Each algorithm is supplied with a Pascal-like program, time complexity in terms of the size of a graph, and worst-case behaviour. In conclusion, some computational results are included with support the estimations and suggest the sequential coloring with interchange algorithm for a largest-first vertex ordering as a method which uses the least number of colors for uniformly distributed random graphs.
Źródło:
Mathematica Applicanda; 1982, 10, 19
1730-2668
2299-4009
Pojawia się w:
Mathematica Applicanda
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Associative graph products and their independence, domination and coloring numbers
Autorzy:
Nowakowski, Richard
Rall, Douglas
Powiązania:
https://bibliotekanauki.pl/articles/972041.pdf
Data publikacji:
1996
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph products
independence
domination
irredundance
coloring
Opis:
Associative products are defined using a scheme of Imrich & Izbicki [18]. These include the Cartesian, categorical, strong and lexicographic products, as well as others. We examine which product ⊗ and parameter p pairs are multiplicative, that is, p(G⊗H) ≥ p(G)p(H) for all graphs G and H or p(G⊗H) ≤ p(G)p(H) for all graphs G and H. The parameters are related to independence, domination and irredundance. This includes Vizing's conjecture directly, and indirectly the Shannon capacity of a graph and Hedetniemi's coloring conjecture.
Źródło:
Discussiones Mathematicae Graph Theory; 1996, 16, 1; 53-79
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Generalized colorings and avoidable orientations
Autorzy:
Szigeti, Jenő
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/971967.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hereditary property
graph coloring
Opis:
Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 1; 137-145
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graph colorings with local constraints - a survey
Autorzy:
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/972031.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
list coloring
choice number
precoloring extension
complexity of algorithms
chromatic number
Opis:
We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered.
In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers $c_v$ for the vertices v ∈ V are given, and the question is whether there can be chosen a subset C(v) ⊆ L(v) of cardinality $c_v$ for each vertex in such a way that the sets C(v),C(v') are disjoint for each pair v,v' of adjacent vertices. The particular case of constant |L(v)| with $c_v$ = 1 for all v ∈ V leads to the concept of choice number, a graph parameter showing unexpectedly different behavior compared to the chromatic number, despite these two invariants have nearly the same value for almost all graphs.
To illustrate typical techniques, some of the proofs are sketched.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 161-228
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the cost chromatic number of outerplanar, planar, and line graphs
Autorzy:
Mitchem, John
Morriss, Patrick
Schmeichel, Edward
Powiązania:
https://bibliotekanauki.pl/articles/971958.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cost coloring
outerplanar
planar
line graphs
Opis:
We consider vertex colorings of graphs in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of the coloring is the sum of the costs incurred at each vertex. The cost chromatic number of a graph with respect to a cost set is the minimum number of colors necessary to produce a minimum cost coloring of the graph. We show that the cost chromatic number of maximal outerplanar and maximal planar graphs can be arbitrarily large and construct several infinite classes of counterexamples to a conjecture of Harary and Plantholt on the cost chromatic number of line graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 229-241
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Spanning trees with many or few colors in edge-colored graphs
Autorzy:
Broersma, Hajo
Li, Xueliang
Powiązania:
https://bibliotekanauki.pl/articles/971955.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
spanning tree
matroid (intersection)
complexity
NP-complete
NP-hard
polynomial algorithm
(minimum) dominating set
Opis:
Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 259-269
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
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ł
Tytuł:
Frequency planning and ramifications of coloring
Autorzy:
Eisenblätter, Andreas
Grötschel, Martin
Koster, Arie
Powiązania:
https://bibliotekanauki.pl/articles/743541.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
frequency assignment
graph coloring
Opis:
This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are T-coloring and list coloring. To model all the subtleties, the techniques of integer programming have proven to be very useful.The ability to produce good frequency plans in practice is essential for the quality of mobile phone networks. The present algorithmic solution methods employ variants of some of the traditional coloring heuristics as well as more sophisticated machinery from mathematical programming. This paper will also address this issue.Finally, this paper discusses several practical frequency assignment problems in detail, states the associated mathematical models, and also points to public electronic libraries of frequency assignment problems from practice. The associated graphs have up to several thousand vertices and range form rather sparse to almost complete.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 51-88
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Three edge-coloring conjectures
Autorzy:
Schelp, Richard
Powiązania:
https://bibliotekanauki.pl/articles/743559.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
Ramsey number
vertex-distinguishing edge-coloring
strong chromatic index
balanced edge-coloring
local coloring
mean coloring
Opis:
The focus of this article is on three of the author's open conjectures. The article itself surveys results relating to the conjectures and shows where the conjectures are known to hold.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 173-182
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hajós theorem for list colorings of hypergraphs
Autorzy:
Benzaken, Claude
Gravier, Sylvain
Skrekovski, Riste
Powiązania:
https://bibliotekanauki.pl/articles/743401.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
list-coloring
Hajós' construction
hypergraph
Opis:
A well-known theorem of Hajós claims that every graph with chromathic number greater than k can be constructed from disjoint copies of the complete graph $K_{k+1}$ by repeated application of three simple operations. This classical result has been extended in 1978 to colorings of hypergraphs by C. Benzaken and in 1996 to list-colorings of graphs by S. Gravier. In this note, we capture both variations to extend Hajós' theorem to list-colorings of hypergraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 2; 207-213
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on total colorings of planar graphs without 4-cycles
Autorzy:
Wang, Ping
Wu, Jian-Liang
Powiązania:
https://bibliotekanauki.pl/articles/744436.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total coloring
planar graph
list coloring
girth
Opis:
Let G be a 2-connected planar graph with maximum degree Δ such that G has no cycle of length from 4 to k, where k ≥ 4. Then the total chromatic number of G is Δ +1 if (Δ,k) ∈ {(7,4),(6,5),(5,7),(4,14)}.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 1; 125-135
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Analogues of cliques for oriented coloring
Autorzy:
Klostermeyer, William
MacGillivray, Gary
Powiązania:
https://bibliotekanauki.pl/articles/744524.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
oriented coloring
clique
planar graph
Opis:
We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 373-387
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Radio k-colorings of paths
Autorzy:
Chartrand, Gary
Nebeský, Ladislav
Zhang, Ping
Powiązania:
https://bibliotekanauki.pl/articles/743194.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
radio k-coloring
radio k-chromatic number
Opis:
For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that
d(u,v) + |c(u)- c(v)| ≥ 1 + k
for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings c of G. In this paper, radio k-colorings of paths are studied. For the path Pₙ of order n ≥ 9 and n odd, a new improved bound for $rc_{n- 2}(Pₙ)$ is presented. For n ≥ 4, it is shown that
$rc_{n-3}(Pₙ) ≤ \binom{n-2} {2}$
Upper and lower bounds are also presented for rcₖ(Pₙ) in terms of k when 1 ≤ k ≤ n- 1. The upper bound is shown to be sharp when 1 ≤ k ≤ 4 and n is sufficiently large.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 1; 5-21
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Some applications of pq-groups in graph theory
Autorzy:
Exoo, Geoffrey
Powiązania:
https://bibliotekanauki.pl/articles/744429.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Ramsey number
edge coloring
cage
degree
girth
Cayley graph
Opis:
We describe some new applications of nonabelian pq-groups to construction problems in Graph Theory. The constructions include the smallest known trivalent graph of girth 17, the smallest known regular graphs of girth five for several degrees, along with four edge colorings of complete graphs that improve lower bounds on classical Ramsey numbers.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 1; 109-114
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Distance coloring of the hexagonal lattice
Autorzy:
Jacko, Peter
Jendrol', Stanislav
Powiązania:
https://bibliotekanauki.pl/articles/744329.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
distance coloring
distant chromatic number
hexagonal lattice of the plane
hexagonal tiling
hexagonal grid
radio channel frequency assignment
Opis:
Motivated by the frequency assignment problem we study the d-distant coloring of the vertices of an infinite plane hexagonal lattice H. Let d be a positive integer. A d-distant coloring of the lattice H is a coloring of the vertices of H such that each pair of vertices distance at most d apart have different colors. The d-distant chromatic number of H, denoted $χ_d(H)$, is the minimum number of colors needed for a d-distant coloring of H. We give the exact value of $χ_d(H)$ for any d odd and estimations for any d even.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 151-166
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 198

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies