Filters
total: 6814
filtered: 5916
-
Catalog
- Publications 5916 available results
- Journals 24 available results
- Conferences 5 available results
- Publishing Houses 1 available results
- People 141 available results
- Inventions 4 available results
- Projects 6 available results
- e-Learning Courses 29 available results
- Events 20 available results
- Open Research Data 668 available results
Chosen catalog filters
displaying 1000 best results Help
Search results for: COST COLORING
-
Optimal edge-coloring with edge rate constraints
PublicationWe consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable....
-
Distributed largest-first algorithm for graph coloring.
PublicationW artykule zaprezentowano rozproszony, probabilistyczny algorytm kolorowania grafów. Kolorowanie uzyskane jest optymalne lub prawie optymalne dla takich klas grafów jak koła dwudzielne, gąsienice czy korony. Udowodniono, że algorytm ten działa w czasie O(D^2 log n) rund dla dowolnego grafu n wierzchołkowegoo stopniu maksymalnym D.
-
Sum coloring of bipartite graphs with bounded degree.
PublicationArtykuł poświęcony jest złożoności obliczeniowej zagadnienia sumacyjnego kolorowania grafów dwudzielnych o ograniczonym stopniu. Zawiera dowód tego, że sumacyjne kolorowanie grafów dwudzielnych stopnia mniejszego równego 5 jest NP-zupełne oraz opis wielomianowego algorytmu, który optymalnie sumacyjnie koloruje grafy dwudzielne podkubiczne.
-
An experimental study of distributed algorithms for graph coloring.
PublicationW pracy podano algorytm rozproszonego kolorowania grafówi porównano ze znanym wcześniej algorytmem.
-
Self-stabilizing algorithm for edge-coloring of graphs
PublicationReferat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu wraz z dowodem poprawności oraz oszacowaniem jego czasu działania.
-
Costs and cost‐effectiveness of the meeting centres support programme for people living with dementia and carers in Italy, Poland and the UK: The MEETINGDEM study
Publication -
The life cycle cost of a building from the point of view of environmental criteria of selecting the most beneficial offer in the area of competitive tendering
PublicationThe article analyses environmental and ecological criteria of selecting the most beneficial offer in the aspect of LCC. Construction works contracts and the potential method of defining the above criteria, among others, is pondered on (for example by the recommendation of a material, which is supposed to be used, a ban on substances that are harmful for human health as well for the environment). In the relation to the above, it...
-
Greedy T-colorings of graphs
PublicationTreścią artykułu są pokolorowania kontrastowe wygenerowane przez algorytm zachłanny. Zbadane zostały ich własności, obejmujące liczbę kolororów, rozpiętość i rozpiętość krawędziową.
-
Parity vertex colouring of graphs
PublicationA parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let Xp(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for...
-
The complexity of the T-coloring problem for graphs with small degree
Publication -
Some results on a trading model in a consensus list coloring
Publication -
A linear time algorithm for edge coloring of binomial trees
Publication -
On the complexity of distributed graph coloring with local minimality constraints
PublicationArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.
-
Some results on trading model in a consensus list coloring
PublicationKonsensusowy model kolorowania grafów - uogólnienie kolorowania listowego, został zdefiniowany przez Mahadeva i Robertsa w 2002 jako użyteczne narzędzie teoretyczne w niektórych zagadnieniach bioinformatycznych. Pozostaje on jednak słabo rozpoznany pod względem własności algorytmicznych. Wykazujemy, że problem kolorowania grafów pełnych w tym modelu jest wielomianowy, co można uogólnić na częściowe k-drzewa przy ustalonym ograniczeniu...
-
Greedy algorithms for backbone graph coloring in KOALA library
Publication -
Optimal backbone coloring of split graphs with matching backbones
PublicationFor a graph G with a given subgraph H, the backbone coloring is defined as the mapping c: V(G) -> N+ such that |c(u)-c(v)| >= 2 for each edge uv \in E(H) and |c(u)-c(v)| >= 1 for each edge uv \in E(G). The backbone chromatic number BBC(G;H) is the smallest integer k such that there exists a backbone coloring with max c(V(G)) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
-
Edge coloring of graphs of signed class 1 and 2
PublicationRecently, Behr (2020) introduced a notion of the chromatic index of signed graphs and proved that for every signed graph (G, σ) it holds that ∆(G) ≤ χ′(G,σ) ≤ ∆(G) + 1, where ∆(G) is the maximum degree of G and χ′ denotes its chromatic index. In general, the chromatic index of (G, σ) depends on both the underlying graph G and the signature σ. In the paper we study graphs G for which χ′(G, σ) does not depend on σ. To this aim we...
-
The complexity of the T-coloring problem for graphs with small degree.
PublicationW pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.
-
On minimum cost edge searching
PublicationWe consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not...
-
Consecutive colorings of the edges of general graphs
Publication -
Compact cyclic edge-colorings of graphs
PublicationArtykuł jest poświęcony modelowi zwartego cyklicznego kolorowania krawędzi grafów. Ten wariant kolorowania jest stosowany w modelowaniu uszeregowań w systemach produkcyjnych, w których proces produkcyjny ma charakter cykliczny. W pracy podano konstrukcje grafów, które nie zezwalają na istnienie pokolorowania w rozważanym modelu. Wykazano także kilka własności teoretycznych, takich jak ograniczenia górne na liczbę kolorów w optymalnym...
-
Colorings of the Strong Product of Circulant Graphs
PublicationGraph coloring is one of the famous problems in graph theory and it has many applications to information theory. In the paper we present colorings of the strong product of several circulant graphs.
-
THE COST ANALYSIS OF CORROSION PROTECTION SOLUTIONS FOR STEEL COMPONENTS IN TERMS OF THE OBJECT LIFE CYCLE COST
PublicationSteel materials, due to their numerous advantages - high availability, easiness of processing and possibility of almost any shaping are commonly applied in construction for carrying out basic carrier systems and auxiliary structures. However, the major disadvantage of this material is its high corrosion susceptibility, which depends strictly on the local conditions of the facility and the applied type of corrosion protection system....
-
Self-stabilizing algorithms for graph coloring with improved performance guarantees
PublicationW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublicationRozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublicationAn edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...
-
A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublicationWe consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with Delta less than or equal to 5, but polynomial on bipartite graphs with Delta less than or equal to 3, for which we construct an O(n(2))-time algorithm. Hence, we tighten the borderline of intractability for this...
-
How Much Does an e-Vote Cost? Cost Comparison per Vote in Multichannel Elections in Estonia
PublicationWe are presenting the results of the CoDE project in this paper, where we investigate the costs per vote of different voting channels in Estonian Local Elections (2017). The elections analyzed involve different processes for casting a vote: Early Voting at County Centers, Advance Voting at County Centers, Advance Voting at Ordinary Voting District Committees, Electronic Voting, Election Day Voting, and Home Voting. Our analysis...
-
Low-cost solutions for Martian base
PublicationZałogowe misje na Marsa planuje się na 2025-30 r. Wg programu DRM NASA misja trwać ma 2,5 roku, a załoga zamieszka w 2 metalowych ciasnych modułach. Jak wykazują badania socjopsychologów taka misja zakończy się niepowodzeniem. Duża i komfortowa baza wpłynie na zminimalizowanie wielu źródeł stresu. Współczesne technologie i obecny stan wiedzy o Marsie pozwalają na zaprojektowanie i wykonanie bazy marsjańskiej jako przyjaznego człowiekowi...
-
Cost minimisation in multi-interface networks
PublicationPraca dotyczy problemu minimalizacji energii poprzez selektywne odłączanie urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne.
-
Cost assessment of computer security activities
PublicationComprehensive cost-benefit analysis plays a crucial role in the decision-making process when it comes to investments in information security solutions. The cost of breaches needs to be analysed in the context of spending on protection measures. However, no methods exist that facilitate the quick and rough prediction of true expenditures on security protection systems. Rafal Leszczyna of Gdansk University of Technology presents...
-
T-colorings, divisibility and circular chromatic number
PublicationLet T be a T-set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T-edge spans espT (G) and espd⊙T (G), where d is a positive integer and d ⊙ T = {0 ≤ t ≤ d (max T + 1): d |t ⇒ t/d ∈ T} . We show that espd⊙T (G) = d espT (G) − r, where r, 0 ≤ r ≤ d − 1, is an integer that depends on T and G. Next we focus on the case T = {0} and show that espd⊙{0} (G) =...
-
Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
Publication -
Computer experiments with a parallel clonal selection algorithm for the graph coloring problem
PublicationArtificial immune systems (AIS) are algorithms that are based on the structure and mechanisms of the vertebrate immune system. Clonal selection is a process that allows lymphocytes to launch a quick response to known pathogens and to adapt to new, previously unencountered ones. This paper presents a parallel island model algorithm based on the clonal selection principles for solving the Graph Coloring Problem. The performance of...
-
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublicationW pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.
-
On Optimal Backbone Coloring of Split and Threshold Graphs with Pairwise Disjoint Stars
Publication -
Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationIn this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.
-
Equitable coloring of graphs. Recent theoretical results and new practical algorithms
PublicationIn 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.
-
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationWe consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublicationIn the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...
-
Cost approach to the flow-shop construction scheduling
Publication -
Cost minimisation in unbounded multi-interface networks
PublicationW pracy badano problem odłączania niektórych urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń przy jednoczesnej minimalizacji zużycia energii. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne dla wariantu, w którym liczba interfejsów komunikacyjnych jest potencjalnie nieograniczona...
-
Simple and low-cost wireless voting system
PublicationThis paper presents the concept of a simple and low-cost wireless voting system working on the 868 MHz frequency band. Described system is dedicated to general shareholders assemblies but it can be easily adapted for other applications. The main advantage is its simplicity and mobility as it consists solely of three components - voting modules, base station and a PC application from which the whole system is managed. This architecture...
-
Low cost microwave X-band generator
PublicationA low cost microwave X-band generator for educational purposes was designed and built. Its simple construction and user's interface makes it suitable for a student laboratory.The generator is based on a single frequency conversion concept. It uses a digitally tunable PLL chip for intermediate frequency generation and an active frequency multiplier for frequency conversion. The generator covers 9,7 - 11 GHz part of the X frequency...
-
Low-Cost Surrogate Models for Microwave Filters
PublicationA novel low-cost kriging-based multivariable parametric macromodeling technique for microwave filters is presented. Kriging is used to model both the residues and poles of a microwave filter's reflection coefficient, and the zeros of the transmission coefficient. The proposed residue-pole-zero (RPZ) technique is demonstrated to efficiently model a high dimensional (8D) microwave filter with pseudoelliptic characteristics.
-
Simple and low-cost wireless voting system
PublicationThis paper presents the concept of a simple and low-cost wireless voting system working in the 868 MHz frequency band. The described system is dedicated to general shareholders assemblies but it can be easily adapted for other applications. The main advantage is its simplicity and mobility as it consists solely of three components - voting modules, a base station and a PC application from which the whole system is mamaged. This...
-
The structure of porous and spontaneously densified amorphous PbSiO3: a Molecular Dynamics study.
PublicationW pracy zaproponowano nową metodę numerycznego otrzymywania strukturporowatych metodą dynamiki molekularnej. Metoda polega na rozpoczęciu symulacji z ładunkami ekranowanymi i stopniowym zwiększaniu ich do pełnych ładunków jonowych. Metodę zastosowano do układu PbSiO3.
-
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
Publication -
A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints
PublicationWe address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem...
-
Consensus models: Computational complexity aspects in modern approaches to the list coloring problem
PublicationArtykuł poświęcony jest nowym modelom konsensusowego kolorowania grafów. Artykuł zawiera omówienie trzech takich modeli, analizę ich złożoności obliczeniowej oraz wielomianowy algorytm dla częściowych k-drzew, dla tzw. modelu addytywnego.