wyświetlamy 1000 najlepszych wyników Pomoc
Wyniki wyszukiwania dla: IMPROPER%20COLORING
-
Some results on a trading model in a consensus list coloring
Publikacja -
A linear time algorithm for edge coloring of binomial trees
Publikacja -
On the complexity of distributed graph coloring with local minimality constraints
PublikacjaArtykuł 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
PublikacjaKonsensusowy 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...
-
The complexity of the T-coloring problem for graphs with small degree.
PublikacjaW pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.
-
Optimal backbone coloring of split graphs with matching backbones
PublikacjaFor 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
PublikacjaRecently, 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...
-
Greedy algorithms for backbone graph coloring in KOALA library
Publikacja -
Proper gradient otopies
PublikacjaWe prove that the inclusion of the space of proper gradient local maps into the space of proper local maps induces a bijection between the sets of the respective otopy classes of these maps.
-
Proper gradient otopies
PublikacjaWe prove that the inclusion of the space of proper gradient local maps into the space of proper local maps induces a bijection between the sets of the respective otopy classes of these maps.
-
Worm Gear Drives with Improved Kinematic Accuracy
PublikacjaThis paper presents the fundamentals of the design and applications of new worm gear drive solutions, which enable the minimisation of backlash and are characterised by higher kinematic accuracy. Different types of worm surfaces are briefly outlined. Technological problems concerning the principles of achieving a high degree of precision in machining are also described. Special attention is paid to the shaping of conical helical...
-
Multiple frequency tracker with improved tracking Capabilities
PublikacjaW pracy zaproponowano prostą modyfikację znanego z literatury wieloczęstotliwościowego adaptacyjnego filtra wycinającego, prowadzącą do istotnej poprawy jego charakterystyk nadążania.
-
An Improved Genetic Algorithm for Island Route Planning
Publikacja -
Advanced laminate composites of improved impact tolerance.
PublikacjaPrzedstawiono przegląd sposobów poprawy tolerancji udarów w nowoczesnych laminatach polimerowych. Są to: wytrzymalsze i bardziej ciągliwe materiały osnowy, dobieranie odpowiedniego powiązania osnowy i włókien, stosowanie włókien w postaci tkanin, zszywanie preform z wielu warstw tkanin, łączenie włókien ciągłych w preformy za pomocą kompozytowych szpilek, stosowanie tkanin NCF z włókien ciągłych łączonych na grubości dodatkowym...
-
Improved method for real-time speech stretching
Publikacjan algorithm for real-time speech stretching is presented. It was designed to modify input signal dependently on its content and on its relation with the historical input data. The proposed algorithm is a combination of speech signal analysis algorithms, i.e. voice, vowels/consonants, stuttering detection and SOLA (Synchronous-Overlap-and-Add) based speech stretching algorithm. This approach enables stretching input speech signal...
-
An improved adaptive neural voltage controller for turbogenerator
PublikacjaOpracowano model adaptacyjnego neuronowego regulatora napięcia z nastrojonym współczynnikiem wzmocnienia funkcji przynależności i z nastrojonym współczynnikiem uczenia sieci neuronowej w zależnosci od stanu obciążenia turbogeneratora. Przedstawiono wyniki symulacji mające na celu badania efektywności proponowanego regulatora. Te wyniki porównano z wynikami uzyskanymi z regulatorem o stałym współczynnikiem wzmocnienia funkcji przynależności...
-
Application of an improved cellular automaton for granular flow.
PublikacjaW artykule omówiono wyniki numeryczne z zastosowaniem ulepszonego aparatu komórkowego do przepływów silosowych materiałów granulowanych. W modelu uwzgledniono zderzenia cząstek i dysypację energii. Wyniki porównano z wynikami badań modelowych.
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublikacjaAn 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
PublikacjaWe 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...
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublikacjaRozważ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.
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Publikacja -
Efficient List Cost Coloring of Vertices and∕or Edges of Some Sparse Graphs
Publikacja -
Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
Publikacja -
Computer experiments with a parallel clonal selection algorithm for the graph coloring problem
PublikacjaArtificial 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...
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublikacjaRozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.
-
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublikacjaW 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)$.
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublikacjaW artykule rozważamy listowo-kosztowe kolorowanie wierzchołków i krawędzi grafu w modelu wierzchołkowym, krawędziowym, totalnym i pseudototalnym. Stosujemy programowanie dynamiczne w celu otrzymania algorytmów wielomianowych dla drzew. Następnie uogólniamy to podejście na dowolne grafy z ograniczonymi liczbami cyklomatycznymi i na ich multikolorowania.
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublikacjaIn 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...
-
On Optimal Backbone Coloring of Split and Threshold Graphs with Pairwise Disjoint Stars
Publikacja -
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublikacjaWe 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.
-
Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs
PublikacjaIn 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
PublikacjaIn 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.
-
A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4
PublikacjaIn the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree ∆≤4 can be solved in O(n^2) time. This extends Jansen’s result [K.Jansen,The optimum cost chromatic partition problem, in:...
-
improved noniterative residue division for small number ranges
Publikacjaw pracy zaprezentowano multiplikatywny algorytm dzielenia w systemie resztowym i projekt 12-bitowego dzielnika dla modułów 5-bitowych. w algorytmie zastosowano obliczanie przybliżonej odwrotności dzielnika i mnozenie przez dzielną. binarna reprezentacja dzielnika jest dekomponowana na dwa segmenty 6-bitowe, co umożliwia obliczenie w środowisku fpga poprzez odwzorowanie realizowane jako odczyt pamięci. w pracy podano udoskonalony...
-
CMOS Low-Dropout Regulator With Improved Time Response
PublikacjaPrzedstawiono nową konfigurację regulatora o obniżonym spadku napięcia, w którym wykorzystano stopień wyjściowy z równoległym sprzężeniem napięciowym. Dzięki obniżonej rezystancji wyjściowej stopnia, uzyskano poprawę odpowiedzi impulsowej regulatora na szybką zmianę prądu wyjściowego.
-
High-speed binary-to-residue converter with improved architecture.
PublikacjaPrzedstawiono ulepszoną architekturę szybkiego konwertera liczb z systemu binarnego do systemu resztowego dla liczb ze znakiem w kodzie U2. Algorytm konwertera oparty jest o segmentację słowa wejsciowego nasegmenty 4-bitowe. Reszty liczb reprezentowanych przez segmenty sąobliczane poprzez odwzorowanie. Wielooperandowe sumowanie modulo jest realizowane przy użyciu drzewa Wallace'a z segmentacją wektorów wyjściowych oraz finalnego...
-
Novel 5.1 Downmix Algorithm with Improved Dialogue Intelligibility
PublikacjaA new algorithm for 5.1 to stereo downmix is introduced, which addresses the problem of dialogue intelligibility. The algorithm utilizes proposed signal processing algorithms to enhance the intelligibility of movie dialogues, especially in difficult listening conditions or in compromised speaker setup. To account for the latter, a playback configuration utilizing a portable device, i.e. an ultrabook, is examined. The experiments...
-
Influence of lubricating oil improvers on performance of crankshaft seals
PublikacjaThis paper presents an original method for checking influence of lubricating oil improvers on performance of crankshaft seals of combustion piston engine. Crankshaft seals were tested with the use of a modified friction node of T-02 four- ball apparatus in laboratory conditions. The tests were conducted according to a worked-out algorithm. Their results confirmed usefulness of the method for determining „harmful” performance...
-
Multistage generalized adaptive notch filter with improved accuracy
PublikacjaGeneralized adaptive notch filters (GANFs) are estimators of coefficients of quasi-periodically time-varying systems. Current state of the art GANFs can deliver highly accurate estimates of system variations’ frequency, but underperform in terms of accuracy of the coefficient estimates. The paper proposes a novel multistage GANF with accuracy improved in this aspect. The processing pipeline consists of three stages. The preliminary...
-
On proper (1,2)‐dominating sets in graphs
PublikacjaIn 2008, Hedetniemi et al. introduced the concept of (1,)-domination and obtained some interesting results for (1,2) -domination. Obviously every (1,1) -dominating set of a graph (known as 2-dominating set) is (1,2) -dominating; to distinguish these concepts, we define a proper (1,2) -dominating set of a graph as follows: a subset is a proper (1,2) -dominating set of a graph if is (1,2) -dominating and it is not a (1,1) -dominating...
-
Gradient versus proper gradient homotopies
PublikacjaWe compare the sets of homotopy classes of gradient and proper gradient vector fields in the plane. Namely, we show that gradient and proper gradient homotopy classi cations are essentially different. We provide a complete description of the sets of homotopy classes of gradient maps from R^n to R^n and proper gradient maps from R^2 to R^2 with the Brouwer degree greater or equal to zero.
-
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
Publikacja -
A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints
PublikacjaWe 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...
-
A note on fast approximate backbone coloring of split graphs with star--like backbones
PublikacjaDla grafu G = (V, E) z wyróżnionym podgrafem H, kolorowanie szkieletowe jest zdefiniowane jako odwzorowanie c spełniające |c(u) - c(v)| > 1 dla każdej krawędzi z E(H) oraz |c(u) - c(v)| > 0 dla każdej krawędzi z E(G). W pracy przedstawiono 1-przybliżony algorytm kolorowania szkieletowego split grafów ze skojarzeniem w szkielecie o złożoności O(|V|) oraz 1-przybliżony algorytm dla split grafów z rozłącznymi gwiazdami w szkielecie.
-
Consensus models: Computational complexity aspects in modern approaches to the list coloring problem
PublikacjaArtykuł 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.
-
The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
PublikacjaGiven a graph G, a spanning subgraph H of G and an integer λ>=2, a λ-backbone coloring of G with backbone H is a vertex coloring of G using colors 1, 2, ..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is to find such a coloring with maximum color that does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree...
-
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
PublikacjaIn 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...
-
Improved methods for stator end winding leakage inductance calculation
PublikacjaCalculating the stator end-winding leakage inductance, taking into account the rotor, is difficult due to the irregular shape of the end-winding. The end-winding leakage may distribute at the end of the active part and the fringing flux of the air gap. The fringing flux belongs to the main flux but goes into the end-winding region. Then, not all the magnetic flux occurring in the end region is the end-winding leakage flux. The...
-
Frequency-Based Regularization for Improved Reliability Optimization of Antenna Structures
PublikacjaThe paper proposes a modified formulation of antenna parameter tuning problem. The main ingredient of the presented approach is a frequency-based regularization. It allows for smoothening the functional landscape of the assumed cost function, defined to encode the prescribed design specifications. The regularization is implemented as a special penalty term complementing the primary objective and enforcing the alignment of the antenna...
-
Improved method of signal processing used in low-coherent systems
PublikacjaW artykule przedstawiono nowe,opracowane metody przetwarzania sygnału w układach niskokoherencyjnych. W układach niskokoherencyjnych z analizą sygnału w dziedzinie czasu zaproponowano wykorzystanie źródeł syntezowanych, natomiast w przypadku układów z przetwarzaniem sygnału w dziedzinie widma zaproponowano metodę opartą na pomiarze przesunięcia widma sygnału pomiarowego. Wyniki przeprowadzonych badań eksperymentalnych zamieszczone...