Search
Search results for: SEMI-EQUITABLE COLORING
-
Structural design and sensitivity analysis of semi-rigid pavement of a motorway
PublicationThis paper presents application of mechanistic-empirical methods in design of semi-rigid pavement for a section of a motorway in Poland. The stage construction was assumed. Three fatigue criteria were applied in the design. For asphalt fatigue cracking and subgrade soil the criteria from the Asphalt Institute (USA) were applied. For fatigue cracking of cement stabilized bases the Dempsey (USA) and De Beer (South Africa) criteria...
-
Interval Edge-Coloring of Graphs
Publication -
Mixed graph edge coloring
PublicationW 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ń.
-
On efficient coloring of chordless graphs
PublicationArtykuł 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
PublicationW 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
PublicationZaproponowano 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].
-
Interval edge-coloring of graphs.
PublicationRozdział 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.
PublicationW 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.
-
Dataset of non-isomorphic graphs of the coloring types (K4,K4;n), 1<n<R(4,4)
Open Research DataFor K4 graph, a coloring type (K4,K4;n) is such an edge coloring of the full Kn graph, which does not have the K4 subgraph in the first color (representing by no edges in the graph) or the K4 subgraph in the second color (representing by edges in the graph).The Ramsey number R(4,4) is the smallest natural number n such that for any edge coloring of...
-
Application of semi-Markov processes for evaluation of diesel engines reliability with regards to diagnostics
PublicationThe paper presents semi-Markov models of technical state transitions for diesel engines, useful for determination of their reliability, as a result of the conducted statistical empirical studies. Interpretation of technical states provided for this sort of engines refers to ship main engines, i.e. engines employed in propulsion systems of sea-going ships. The considerations recognize diesel engine as a diagnosed system (SDN), of...
-
Structural Design and Sensitivity Analysis of Semi-Rigid Pavement of a Motorway
PublicationThis paper presents application of mechanistic-empirical methods in design of semi-rigid pavement for a section of a motorway in Poland. The stage construction was assumed. Three fatigue criteria were applied in the design. For asphalt fatigue cracking and subgrade soil the criteria from the Asphalt Institute (1981) were applied. For fatigue cracking of cement stabilized bases the Dempsey (1984) and De Beer (1992) criteria were...
-
USEFULNESS OF SEMI-MARKOV PROCESSES AS MODELS OF THE OPERATION PROCESSES FOR MARINE MAIN ENGINES AND OTHER MACHINES OF SHIP POWER PLANTS
PublicationThe paper describes the properties of semi-Markov processes and the opportunities and benefits from their use as models of the operation processes for marine combustion engines and other machines of ship power plants. The emphasis is put on the importance of the theory of semi-Markov processes for development of the theory of marine combustion engines and other machines of ship power plants, as well as for development of the operational...
-
Experimentally feasible semi-device-independent certification of four-outcome positive-operator-valued measurements
PublicationRecently the quantum information science community devoted a lot of attention to the theoretical and practical aspects of generalized measurements, the formalism of all possible quantum operations leading to acquisition of classical information. On the other hand, due to imperfections present in quantum devices, and limited thrust to them, a trend of formulating quantum information tasks in a semi-device-independent manner emerged....
-
Ocena przydatności stosowania komory semi-bezechowej w przyczepie badawczej SLIPSONIC służącej do pomiarów hałasu opon.
PublicationOmówiono sposoby pomiaru odbić dźwięku oraz izolacyjności komory semi-bezechowej zastosowanej w przyczepie SLIPSONIC. Przedstawiono wyniki badań wykazujących jednoznacznie konieczność stosowania komór semi-bezechowych w przyczepach do badania hałasu opon.
-
On greedy graph coloring in the distributed model
PublicationArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Zaprezentowano nowy probabilistyczny algorytm dający w wyniku pokolorowanie LF. Udowodniono, że jakakolwiek rozproszona implementacja LF wymaga co najmniej D rund, gdzie D jest maksymalnym stopniem wierzchołka w grafie.
-
Edge-coloring of 3-uniform hypergraphs
PublicationWe 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.
-
Dataset of non-isomorphic graphs of the coloring types (K3,Km;n), 2<m<7, 1<n<R(3,m)
Open Research DataFor K3 and Km graphs, a coloring type (K3,Km;n) is such an edge coloring of the full Kn graph, which does not have the K3 subgraph in the first color (representing by no edges in the graph) or the Km subgraph in the second color (representing by edges in the graph).The Ramsey number R(3,m) is the smallest natural number n such that for any edge coloring...
-
The surface of a fragment of the structure of an integrated circuit in the semi-contact mode.
Open Research DataThe surface of a fragment of the structure of an integrated circuit. Topographic measurements in the semi-contact mode. NTEGRA Prima (NT-MDT) device. NSG 01 probe.
-
Concrete temperature measurements of cubic specimens cured under isothermal and semi-adiabatic conditions
Open Research DataThe DataSet contains temperature measurements of concrete cubes (150 x 150 x 150 mm) cured under isothermal and semi-adiabatic conditions. The specimens were moulded from six types of concrete mixtures produced in the laboratory conditions. Mix #1: Portland cement CEM I 42.5R and gravel aggregate, mix #2: CEM I 42.5R and basalt aggregate, mix#3: Portland-composite...
-
Application of the theory of semi-markov processes to the development of a reliability model of an automotiv vrhicle = Zastosowanie teorii procesów semi-Markowa do opracowania modelu niezawodnościowego samochodu
PublicationW artykule przedstawiono możliwość zastosowania teorii procesów semi-Markowa (semimarkowskich) do opisu niezawodności samochodu, na przykładzie samochodu osobowego. W rozważaniach uwzględniony został samochód, w którym wyróżniono takie węzły konstrukcyjne (zespoły funkcjonalne) jak: silnik z układami zasilania czynnikami energetycznymi (paliwem, olejem smarowym i cieczą chłodzącą), sprzęgło, skrzynia biegów, wał napędowy, most...
-
Increased Certification of Semi-device Independent Random Numbers using Many Inputs and More Postprocessing
PublicationQuantum communication with systems of dimension larger than two provides advantages in information processing tasks. Examples include higher rates of key distribution and random number generation. The main disadvantage of using such multi-dimensional quantum systems is the increased complexity of the experimental setup. Here, we analyze a not-so-obvious problem: the relation between randomness certification and computational requirements...
-
Dataset of non-isomorphic graphs of the coloring types (K3,Km-e;n), 2<m<7, 1<n<R(K3,Km-e).
Open Research DataFor K3 and Km-e graphs, a coloring type (K3,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K3 subgraph in the first color (representing by no edges in the graph) or the Km-e subgraph in the second color (representing by edges in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K3,Km-e)...
-
Dataset of non-isomorphic graphs of the coloring types (Km,K3-e;n), 4<m<8, 1<n<R(Km,K3-e)
Open Research DataFor Km and K3-e graphs, a coloring type (Km,K3-e;n) is such an edge coloring of the full Kn graph, which does not have the Km subgraph in the first color (representing by no edges in the graph) or the K3-e subgraph in the second color (representing by edges in the graph). K3-e means the full Km graph with one edge removed.The Ramsey number R(Km,K3-e)...
-
Enhancing seismic performance of rigid and semi-rigid connections equipped with SMA bolts incorporating nonlinear soil-structure interaction
PublicationNowadays, using smart connections can improve the performance of buildings with some recentering features that are from the superelastic behavior of Shape Memory Alloys (SMAs). It seems that there is different rigidity between the designed connection and the real one in Steel Moment-Resisting Frames (SMRFs), which can be considered as a problematic issue due to the importance of connections in seismic performance assessment. This...
-
Sum Coloring of Bipartite Graphs with Bounded Degree
Publication -
A better practical algorithm for distributed graph coloring
Publication -
Interval vertex-coloring of a graph with forbidden colors
Publication -
Interval Vertex-Coloring of a Graph With Forbidden Colors
Publication -
Interval edge coloring of a graph with forbidden colors
Publication -
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.
-
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....
-
New potential functions for greedy independence and coloring
PublicationA potential function $f_G$ of a finite, simple and undirected graph $G=(V,E)$ is an arbitrary function $f_G : V(G) \rightarrow \mathbb{N}_0$ that assigns a nonnegative integer to every vertex of a graph $G$. In this paper we define the iterative process of computing the step potential function $q_G$ such that $q_G(v)\leq d_G(v)$ for all $v\in V(G)$. We use this function in the development of new Caro-Wei-type and Brooks-type...
-
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.
-
Synthesis and characterisation of polyurethane elastomers with semi-products obtained from polyurethane recycling
PublicationIn this work polyurethane elastomers were synthesised by using different mixtures of a petrochemical and glycerolysate polyols and 4,4-diphenylmethane diisocyanate (MDI). Glycerolysate polyol was produced from polyurethane foam decomposition using crude glycerine as a decomposition agent. The structure and thermal properties of obtained semi-product were similar to the polyol used in the synthesis of original foam. Glycerolysate...
-
Assesment of operation of ship main diesel engine using the theory of semi-markovian and markov processes.
PublicationTo precisely determine the task it is necessary to specify also its duration time, apart from conditions in which it will be realized. When considering propulsion engine, i.e. the main element of ship propulsion system, especially important becomes not only the problem which amount of energy could be at one's disposal but also within which time interval it could be delivered. Therefore apart from applying the commonly used reliability...
-
Dataset of non-isomorphic graphs of the coloring types (K4,Km-e;n), 2<m<5, 1<n<R(K4,Km-e)
Open Research DataFor K4 and Km-e graphs, a coloring type (K4,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K4 subgraph in the first color (representing by no edges in the graph) or the Km-e subgraph in the second color (representing by edges in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K4,Km-e)...
-
Testing and sampling devices for monitoring volatile and semi-volatile organic compounds in indoor air
PublicationAdults spend most of their time in enclosed spaces (e.g., apartment, office and public buildings). According to research conducted by scientists, air quality indoors is much worse than the ambient air quality outdoors. Hazardous chemicals found in air indoors can adversely affect the functioning of the human body and cause many respiratory and circulatory diseases. Harmful chemical compounds (mainly volatile organic compounds and...
-
Ecology and Conservation of Steppes and Semi-Natural Grasslands
Publication -
Semi-Markov Approach to the Shipping Safety Modelling
Publication -
Application Isssues of the Semi-Markov Reliability Model
PublicationPredicting the reliability of marine internal combustion engines, for instance, is of particular importance, as it makes it possible to predict their future reliability states based on the information on the past states. Correct reliability prediction is a complex process which consists in processing empirical results obtained from operating practice, complemented by analytical considerations. The process of technical state changes...
-
Investigations of transverse stability of semi-displacement ships
PublicationPrzedstawiono wyniki eksperymentalnych badań modelowych poprzecznej stateczności jednostek półślizgowych, których celem było określenie wpływu prędkości oraz parametrów kształtu kadłuba na stateczność poprzeczną. Na podstawie wyników badań opracowano algorytmy, uwzględniające zmiany ramienia prostującego w funkcji prędkości, kąta przechyłu i parametrów geometrycznych kadłuba które mogą być wykorzystane do oceny stateczności poprzecznej...
-
A semi-empirical model for flow boiling heat transfer with account of the reduced pressure effect
PublicationIn the present study the attention was focused on the influence of reduced pressure on the predictions of heat transfer during flow boiling at the extensive range of pressures. The results of calculations were to test the sensitivity of the in-house flow boiling model with respect to the selection of the appropriate two-phase flow multiplier, which is one of the distinctive elements of that model. For this purpose a few two-phase...
-
Dataset of non-isomorphic graphs being coloring types (K3-e,Km-e;n), 2<m<8, 1<n<R(K3-e,Km-e)
Open Research DataFor K3-e and Km-e graphs, the type coloring (K3-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K3-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K3-e,Km-e) is the smallest...
-
COMPARATIVE ANALYSIS OF RESULTS OF APPLICATION OF MARKOV AND SEMI-MARKOV PROCESSES TO RELIABILITY MODELS OF MULTI-STATE TECHNICAL OBJECTS
PublicationDuring rational operation of technical objects and systems various operational decisions are made and decision-making process itself should be consisted in selecting that considered most favourable out of all possible to be taken. Choice of such decision is possible after taking into account many different information items but it never be completely correct without accounting for data and indices dealing with reliability. In...
-
The time of the first transition of the semi-Markov process in the evaluation of diesel engine operation
PublicationW referacie przedstawiono rozwinięcie prezentowanej w literaturze metody ilościowej oceny działania na przykładzie okrętowego silnika głównego z zapłonem samoczynnym. Według tej interpretacji, działanie silnika może zostać przedstawione jako wielkość fizyczna. W tym aspekcie, na przykładzie okrętowego silnika napędu głównego dokonano oceny przydatności tej wielkości do opisu własności niezawodnościowych silnika. Precyzyjne określenie...
-
Dataset of non-isomorphic graphs being coloring types (K4-e,Km-e;n), 2<m<7, 1<n<R(K4-e,Km-e)
Open Research DataFor K4-e and Km-e graphs, the type coloring (K4-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K4-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K4-e,Km-e) is the smallest...
-
Dataset of non-isomorphic graphs being coloring types (K5-e,Km-e;n), 2<m<5, 1<n<R(K5-e,Km-e)
Open Research DataFor K5-e and Km-e graphs, the type coloring (K5-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K5-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K5-e,Km-e) is the smallest...
-
Dataset of non-isomorphic graphs being coloring types (K6-e,Km-e;n), 2<m<5, 1<n<R(K6-e,Km-e)
Open Research DataFor K6-e and Km-e graphs, the type coloring (K6-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K6-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed. The Ramsey number R(K6-e,Km-e) is the smallest...