Wyszukiwarka
Wyniki wyszukiwania dla: INCIDENCE%20COLORING
-
Interval incidence graph coloring
PublikacjaIn this paper we introduce a concept of interval incidence coloring of graphs and survey its general properties including lower and upper bounds on the number of colors. Our main focus is to determine the exact value of the interval incidence coloring number χii for selected classes of graphs, i.e. paths, cycles, stars, wheels, fans, necklaces, complete graphs and complete k-partite graphs. We also study the complexity of the...
-
Interval incidence coloring of subcubic graphs
PublikacjaIn this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is N P-complete, and they asked if χii(G) ≤ 2∆(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with ∆(G) = 3.
-
Interval incidence coloring of bipartite graphs
PublikacjaIn this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic...
-
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublikacjaIn the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.
-
Innovations in Incidence Geometry
Czasopisma -
iScience
Czasopisma -
A Novel Approach to the Assessment of Cough Incidence
PublikacjaIn this paper we consider the problem of identication of cough events in patients suffering from chronic respiratory diseases. The information about frequency of cough events is necessary to medical treatment. The proposed approach is based on bidirectional processing of a measured vibration signal - cough events are localized by combining the results of forward-time and backward-time analysis. The signal is at rst transformed...
-
Determinants of the incidence of non-academic staff in European and US HEIs
PublikacjaIn this article, we contribute to the scant literature covering quantitative studies on the determinants of the non-academic staff incidence in higher education institutions by analysing how the proportion of non-academic staff is related to key features such as size, prestige, year of foundation and financial structure of universities. We apply nonlinear regression analysis to compare HEIs across Europe and the USA, taking into...
-
Radiation phenomena from pseudochiral cylinders at plane wave incidence
PublikacjaPrzedstawiono wpływ materiałów pseudochiralnych na charakterystyki rozproszenia fali elektromagnetycznej od obiektów cylindrycznych. W celu zbadania zjawisk rozproszenia zastosowano kombinacje iteracyjnej procedury rozproszenia i metodę dopasowania rodzajów. Wpływ zastosowania materiałów pseudochiralych w konfiguracjach obiektów cylindrycznych zaprezentowano na charakterystykach pola rozproszonego w strefie dalekiej oraz na charakterystykach...
-
Radiation phenomena from metamaterial cylinders at oblique plane wave incidence.
PublikacjaW pracy przedstawiono wpływ ujemnej przenikalności elektrycznej i magnetycznej rezonatorów cylindrycznych umieszczonych w wolnej przestrzeni na parametry rozproszenia. Wykorzystano zmodyfikowaną procedurę iteracyjną i metodę dopasowania rodzajów w celu badania fali rozproszonej od układu cylindrów przy ukośnym padaniu fali płaskiej.
-
A EuroPrevall review of factors affecting incidence of peanut allergy: priorities for research and policy
Publikacja -
Incidence and Clinical Course of Respiratory Viral Coinfections in Children Aged 0–59 Months
Publikacja -
The incidences of other primary cancers in patients with mycosis fungoides and Sézary syndrome
Publikacja -
Does social–economical transformation influence the incidence of type 1 diabetes mellitus? A Polish example
Publikacja -
Automatic Incident Detection at Intersections with Use of Telematics
PublikacjaWhile there are many examples of Intelligent Transport System deployments in Poland, more attention should be paid to traffic incident management and detection on dual-carriageways and urban street networks. One of the aims of CIVITAS DYN@MO, a European Union funded project, is to use TRISTAR (an Urban Transport Management System) detection modules to detect incidents at junctions equipped with traffic signals. First part of paper...
-
Modelling the loss of time caused by traffic incidents on motorways
PublikacjaFor each road incident important factors like location, capacity reduction, traffic management, duration of road incidents and amount of traffic should be defined. All performer operations and effects of incidents affect the capacity of the road, average speed, time loss, vehicle queues and traffic jams. In the article road incidents were divided into planned and unexpected. Statistical analysis prepared using the database of traffic...
-
Dynamic coloring of graphs
PublikacjaDynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In...
-
Equitable coloring of hypergraphs
PublikacjaA hypergraph is equitablyk-colorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin any two color classes differs by at most one. We prove that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomial-time algorithm to...
-
Rank Coloring of Graphs.
PublikacjaRozdział jest poświęcony uporządkowanemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Harmonions Coloring of Graphs.
PublikacjaProblem kolorowania grafów jest motywowany radionawigacją lotniczą, kompresją obrazów i in. W rozdziale podano podstawowe fakty dotyczące tego modelu kolorowania, a wsród nich dolne i górne oszacowania na liczbę harmoniczną i algorytm o złożoności 0 (mm3) dający bardzo dobre pokolorowania przybliżone.
-
T-coloring of graphs.
PublikacjaNiniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana została jego definicja i podstawowe własności, zastosowania oraz złożoność obliczeniowa problemów rozważanych w ramach tej dziedziny.
-
Classical coloring of graphs.
PublikacjaRozdział obejmuje klasyczne kolorowanie krawędzi i wierzołków w grafach prostych. Oprócz podstawowych definicji podane zostały najczęściej stosowane metody przybliżone oraz ich właściwości. Dodatkowo rozdział zawiera przegląd znanych benczmarków dla podanych metod w kontekście klasycznego modelu kolorowania.
-
Sum Coloring of Graphs.
PublikacjaRozdział jest poświęcony sumacyjnemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Examination method of the effect of the incidence angle of laser beam on distance measurement accuracy to surfaces with different colour and roughness
PublikacjaInterest in the influence of the incidence angle of a laser beam to distance measurements can be seen in many areas of science and technology: geodesy, glaciology, archaeology, machine automation, and others. This paper presents results of measurements of the effect of the incidence angle of a laser beam to distance measurements to the surfaces of different colour and roughness by Topcon's electro-optical total station with an...
-
Incidence of type 1 diabetes among Polish children ages 0–14 years from 1989–2012
Publikacja -
Rapid increase in the incidence of type 1 diabetes in Polish children from 1989 to 2004, and predictions for 2010 to 2025
Publikacja -
Incidence of severe critical events in paediatric anaesthesia (APRICOT): a prospective multicentre observational study in 261 hospitals in Europe
Publikacja -
Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring
PublikacjaA graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...
-
Updated 24-year trend of Type 1 diabetes incidence in children in Poland reveals a sinusoidal pattern and sustained increase
Publikacja -
The influence of harvest maturity and basic macroelement content in fruit on the incidence of diseases and disorders after storage of the ‘Ligol’ apple cultivar
Publikacja -
Koala graph coloring library: an open graph coloring library for real-world applications
PublikacjaPomimo intensywnej pracy naukowej na polu kolorowania grafów, nie jest znana kompletna i dedykowana biblioteka programistyczna. Celem artykułu jest zaproponowanie architektury takiej biblioteki. Celem jest spełnienie oczekiwań wypływających z rzeczywistych zastosowań, w szczególności spełnienie potrzeb wydajnościowych. Zaimplementowano szereg algorytmów cheurystycznego kolorowania grafów. Przyjętym językiem programowania jest C++....
-
On-line P-coloring of graphs
PublikacjaFor a given induced hereditary property P, a P-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property P. We consider the effectiveness of on-line P-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function...
-
Interval Edge-Coloring of Graphs
Publikacja -
On efficient coloring of chordless graphs
PublikacjaArtykuł omawia zagadnienie optymalnego, wielomianowego rozpoznawania i kolorowania grafów bezcięciwowych. Zawiera dowód tego, że takie grafy są zawsze 4-kolorowalne oraz opis wielomianowego algorytmu, który koloruje je minimalną możliwą liczbą kolorów.
-
On the complexity of distributed greedy coloring
PublikacjaW pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.
-
A note on mixed tree coloring
PublikacjaZaproponowano liniowy algorytm dla problemu kolorowania mieszanego w drzewach, uzyskując tym samym poprawę w stosunku do algorytmu o złożoności O(n^2) podanego w pracy [P. Hansen, J. Kuplinsky, D. de Werra, Mixed graph colorings, Math. Methods Oper. Res. 45 (1997) 145-160].
-
Mixed graph edge coloring
PublikacjaW pracy rozważany jest problem kolorowania krawędzi grafu mieszanego, tj. grafu zawierającego zawiero skierowane, jak i nieskierowane krawędzie. Motywację do badań stanowią zagadnienia komunikacyjne z zakresu szeregowania zadań.
-
2-Coloring number revisited
Publikacja2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow...
-
Interval edge-coloring of graphs.
PublikacjaRozdział poświęcony prezentacji modelu zwartego kolorowania krawędziowego grafów i jego znanych własności. Szczególny nacisk położono na opis klas grafów dających się pokolorować zwarcie w czasie wielomianowym. Omówiono także stratność jako miarę niepodatności grafu na kolorowanie zwarte.
-
Path Coloring and Routing in Graphs.
PublikacjaW rozdziale omówione zostały problemy kolorowania ścieżek i routingu w grafach. Podano podstawowe definicje związane z tymi problemami, znane wyniki wraz z dyskusją złożoności obliczeniowej dla grafów ogólnych i dla kilku podstawowych klas grafów oraz zastosowania.
-
Equitable vertex coloring of graphs
PublikacjaW pracy podajemy wartości sprawiedliwej liczby chromatycznej dla niektórych klas grafów. Podajemy również dwa algorytmy heurystyczne dla sprawiedliwego kolorowania grafów z suboptymalna liczba koloru.
-
Incidence of Post-operative Gastro-esophageal Reflux Disorder in Patients Undergoing Laparoscopic Sleeve Gastrectomy: A Systematic Review and Meta-analysis
Publikacja -
Security Requirements and Controls for Incident Information Sharing in the Polish Power System
PublikacjaAmong the strategies of protecting information assets of the power system, sharing of information about current cybersecurity incidents between energy operators appears to be a prerequisite. Exchange of information leads to the effective detection of attacks and exploited vulnerabilities as well as the identification of countermeasures. This paper presents the results of continuation of our works on developing a secure and efficient...
-
Rectangular microstrip resonator illumi-nated by normal-incident plane wave
PublikacjaW pracy przedstawiono koncepcję modów oświetlających pozwalającą na obliczenie podstawowych parametrów elektrycznych anten mikropaskowych - częstotliwości rezonansowej, rezystancji promieniowania i charakterystyki promieniowania. Oparta jest ona na dwuwymiarowej metodzie przestrzeni widmowej, w której pobudzenie występuje w formie pojedynczej fali płaskiej padającej prostopadle na analizowaną strukturę. Rezultatem takiego podejścia...
-
Equitable coloring of corona multiproducts of graphs
PublikacjaWe give some results regarding the equitable chromatic number for l-corona product of two graphs: G and H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G.
-
Dynamic F-free Coloring of Graphs
PublikacjaA problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...
-
Edge-coloring of 3-uniform hypergraphs
PublikacjaWe consider edge-colorings of 3-uniform hypergraphs which is a natural generalization of the problem of edge-colorings of graphs. Various classes of hypergraphs are discussed and we make some initial steps to establish the border between polynomial and NP-complete cases. Unfortunately, the problem appears to be computationally difficult even for relatively simple classes of hypergraphs.
-
The Backbone Coloring Problem for Small Graphs
PublikacjaIn this paper we investigate the values of the backbone chromatic number, derived from a mathematical model for the problem of minimization of bandwidth in radio networks, for small connected graphs and connected backbones (up to 7 vertices). We study the relationship of this parameter with the structure of the graph and compare the results with the solutions obtained using the classical graph coloring algorithms (LF, IS), modified...
-
The Backbone Coloring Problem for Bipartite Backbones
PublikacjaLet G be a simple graph, H be its spanning subgraph and λ≥2 be an integer. By a λ -backbone coloring of G with backbone H we mean any function c that assigns positive integers to vertices of G in such a way that |c(u)−c(v)|≥1 for each edge uv∈E(G) and |c(u)−c(v)|≥λ for each edge uv∈E(H) . The λ -backbone chromatic number BBCλ(G,H) is the smallest integer k such that there exists a λ -backbone coloring c of G with backbone H satisfying...
-
The complexity of equitable vertex coloring graphs
PublikacjaW artykule podajemy wzory na sprawiedliwą liczbę chromatyczną niektórych produktów grafowych. Ponadto przedstawiamy dwa algorytmy wielomianowe dla sprawiedliwego kolorowania grafów suboptymalną liczba kolorów.