Search results for: SEMI-EQUITABLE COLORING
-
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 -
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.
-
Greedy algorithms for backbone graph coloring in KOALA library
Publication -
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...
-
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...
-
Semi-transparent ordered TiO2 nanostructures prepared by anodization of titanium thin films deposited onto the FTO substrate
PublicationIn a significant amount of cases, the highly ordered TiO2nanotube arrays grow through anodic oxidationof a titanium metal plate immersed in electrolyte containing fluoride ions. However, for some practicalapplications, e.g. solar cells or electrochromic windows, the semi-transparent TiO2formed directly onthe transparent, conductive substrate is very much desired. This work shows that high-quality Ti coatingcould be formed at room...
-
A model of fuel combustion process in the marine reciprocating engine work space taking into account load and wear of crankshaft-piston assembly and the theory of semi-Markov processes
PublicationThe ar ticle analyses the operation of reciprocal internal combu stion engines, with mar ine engines u sed a s an example. The analysis takes into account types of energy conversion in the work spaces (cylinders) of these engines, loads of their crankshaft-piston assemblies, and types of fuel combustion which can take place in these spaces during engine operation. It is highlighted that the analysed time-dependent loads of marine...
-
Morphology and local chain structure of polyamide 6 modified in the solid state with a semi-aromatic nylon salt
PublicationStructural and conformational differences between the polyamide 6 (PA6) homopolymer and two copolymers of PA6 modified in the solid state with 20 and 30 wt% of the semi-aromatic nylon salt of 1,5-diamino-2-methylpentane (Dytek A) and isophthalic acid (IPA) in the feed were investigated. Room temperature wide-angle X-ray diffraction (WAXD) analysis together with 13C{1H} cross-polarization/magic-angle spinning solid-state (CP/MAS)...
-
Semi-incremental addition of strings to a cyclic finite automaton
PublicationMaszyny o skończonej liczbie stanów są szeroko stosowane jako słowniki w przetwarzaniu języka naturalnego. Odznaczają się szybkim czasem przetwarzania i małymi wymaganiami pamięciowymi. Przedstawiamy nowy algorytm dodawania nowych słów do języka cyklicznego automatu skończonego. Algorytm jest rozszerzeniem na automaty cykliczne półprzyrostowego algorytmu Watsona dla automatów acyklicznych. Przekształcenie jest dokonane w duchu...
-
Semi-Markov model of diesel engines' operating process.
PublicationNajistotniejszym problemem eksploatacji silników o zapłonie samoczynnym jest problem racjonalnego (a zwłaszcza optymalnego) sterowania procesem eksploatacji tych silników. Sterowanie takie może ułatwić zastosowanie iteracyjnego algorytmu wyznaczania optymalnych strategii opracowanego przez R.A. Howarda. Wykorzystanie jednak tego algorytmu do sterowania procesem eksploatacji silników wymaga między innymi opracowania modelu procesu...
-
Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata
PublicationPrzedstawione zostają modyfikacje trzech algorytmów przyrostowego i półprzyrostowego tworzenia automatów minimalnych w taki sposób, aby tworzyły automaty pseudominimalne. Istniejący od dawna algorytm Revuza tworzy takie automaty szybciej i zużywając mniej pamięci, ale wymaga kłopotliwego sortowania. Nie nadaje się też do dodawania nowych słów do automatu - ważnej czynności w realizacji dynamicznej doskonałej funkcji mieszającej....
-
Semi complex navigation with an active optical gesture sensor
PublicationThis paper presents the methods of diversified touchless interactions between a user and a mobile platform utilizing the optical gesture sensor. The sensor uses 8 photodiodes to measure the reflected light in the active mode (using embedded LEDs) or it measures shadows caused by fingers in the passive mode. Several algorithms were implemented: automatic mode switching, adaptive illumination level compensation, resolution improvements...
-
Semi-adaptive feedback active control of MRI noise
PublicationA feedback controller is proposed for cancellation of magnetic resonance imaging (MRI) noise. The design of the controller takes into account specific features of the MRI noise signal. Simulation results show that a considerable rejection rate of the MRI noise can be obtained.
-
Determination of rectification corrections for semi gantry crane rail axes in the local 3D coordinate system
PublicationElectronic tacheometers are currently the standard instruments used in geodetic work, including also geodetic engineering measurements. The main advantage connected with this equipment is among others high accuracy of the measurement and thus high accuracy of the final determinations represented for example by the points’ coordinates. One of many applications of the tacheometers is the measurement of crane rail axes. This measurement...
-
Bandwidth-Controllable Third-Order Band Pass Filter Using Substrate Integrated Full- and Semi-Circular Cavities
PublicationThe article presents a novel circular substrate integrated waveguide (SIW) bandpass filter (BPF) with controllable bandwidth. The proposed BPF is configured using two microstrip feedlines, semi- circular SIW cavities, capacitive slots, and inductive vias. The circular cavity is bisected into two halves, with the two copies thereof being cascaded. Two bisected and cascaded structures obtained this way are subsequently connected...
-
Necessity for and possibility of application of the theory of semi-markov processes to determine reliability of diagnising systems
PublicationW opracowaniu uzasadniono konieczność określenia niezawodności systemów diagnozujących (SDG) do sformułowania diagnozy o stanie dowolnego urządzenia technicznego jako systemu diagnozowanego (SDN). Wykazano, że znajomość niezawodności SDG umożliwia określenie wiarygodności diagnozy. Przyjęto, że wiarygodność diagnozy może być określona jako właściwość diagnozy określająca stopień rozpoznania przez system diagnozujący (SDG) rzeczywistego...
-
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...
-
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.
-
Enhancing Seismic Performance of Semi-rigid Connection Using Shape Memory Alloy Bolts Considering Nonlinear Soil–Structure Interaction
PublicationSteel Moment-Resisting Frames (SMRFs) have their lateral resistance for their rigid connections, while real conditions have shown that the rigidity of a connection depends on the bolts and the end-plate thickness, which may not provide the assumed rigidity in design process. In this research, the main goal is to enhance the semi-rigid connections using shape memory alloy (SMA) bolts and explore their effects on the seismic limit-state...
-
The influence of phosphorus fractions in bottom sediments on phosphate removal in semi-natural systems as the 3rd stage of biological wastewater treatment
PublicationThe research was carried out in two semi-natural systems (the polishing ponds in Swarzewo and the free water surface constructed wetland in Zarnowiec) in Poland. They were built as the 3rd stage of a conventional mechanical–biological wastewater treatment plant. These systems were built to improve the quality of the effluent of treated wastewater. In the polishing ponds and FWS wetland system, suspended solids, organic matter as...
-
Study on effective front region thickness of PCM in thermal energy storage using a novel semi-theoretical model
PublicationThermal energy storage in mobile applications, particularly battery of electric vehicles, is currently gaining a lot of importance. In this paper, a semi-theoretical time-dependent mathematical model of the phase change in a double shell thermal energy storage module has been developed where the inner tube is a heat exchange surface. An effective front region thickness for the melting and solidification process has been studied....
-
Ammonia amendment promotes high rate lactate production and recovery from semi-continuous food waste fermentation
PublicationIn this study, a reliable approach using ammonia nitrogen was proposed to increase lactate production during semi-continuous food waste (FW) fermentation under mesophilic conditions. Both free ammonia nitrogen (FAN) and ammonium ion (NH4+-N) were present in mesophilic reactors, with a wide FAN/NH4+-N ratio variation due to the intermittent pH control. The investigation of responsible mechanisms revealed that the increased production...
-
Modelling of saturated, subcooled and post-dryout flow boiling with the energy dissipation based semi-empirical model
PublicationA comprehensive semi-empirical model for saturated, subcooled and post dryout heat transfer is presented based on considerations of energy dissipation in the flow. The fundamental hypothesis in the model is the fact that heat transfer during flow boiling can be treated as a sum of two contributions constituting the total energy dissipation in the flow, namely the energy dissipation due to the shearing flow without the bubbles and...
-
Visually validated semi-automatic high-frequency oscillation detection aides the delineation of epileptogenic regions during intra-operative electrocorticography
PublicationOBJECTIVE: To test the utility of a novel semi-automated method for detecting, validating, and quantifying high-frequency oscillations (HFOs): ripples (80-200 Hz) and fast ripples (200-600 Hz) in intra-operative electrocorticography (ECoG) recordings. METHODS: Sixteen adult patients with temporal lobe epilepsy (TLE) had intra-operative ECoG recordings at the time of resection. The computer-annotated ECoG recordings were visually...
-
A semi-Markov model of fuel combustion process in a Diesel engine
PublicationW artykule przedstawiono czterostanowy model procesu spalania w przestrzeniach roboczych (cylindrach) silników o zapłonie samoczynnym w formie procesu semimarkowskiego, dyskretnego w stanach i ciągłego w czasie. Wartościami tego procesu są stany odpowiadające powszechnie akceptowanym rodzajom spalania w tego rodzaju silnikach a mianowicie takie stany procesu jak: spalanie pełne (całkowite i zupełne), spalanie niezupełne, spalanie...
-
Determination of Vehicles Load Equivalency Factors for Polish Catalogue of Typical Flexible and Semi-rigid Pavement Structures
PublicationThe new Polish Catalog of Typical Flexible and Semi-rigid Pavement Structures was introduced to use in practice in 2014. Much of works were focused on actualization of vehicles load equivalency factors. For this purpose data delivered from weigh-inmotion were analyzed. Four methods of determination of load equivalency factors for pavement structure design were compared. The analysis showed that fourth power equation, AASHTO 1993...
-
The semi-Markov model of the process of appearance of sea-going ship propupsion system ability and inability states in application to determining the reliablity of these systems
PublicationThe article presents possible application of the theory of semi-Markov processes in creating the eight-state model of the process of appearance of the propulsion systems ability and inability states on sea-going vessels performing transportation tasks in a relatively long operating time t (t → ∞). The model has been proved to be able to be successfully used for determining the reliability of the abovementioned systems. The probability...
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublicationW 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.
-
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)$.
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublicationRozważ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.
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Publication -
Efficient List Cost Coloring of Vertices and∕or Edges of Some Sparse Graphs
Publication -
On Optimal Backbone Coloring of Split and Threshold Graphs with Pairwise Disjoint Stars
Publication -
Unconventional and user-friendly sampling techniques of semi-volatile organic compounds present in an indoor environment: An approach to human exposure assessment
PublicationThe commonly applied solutions used to assess the potential risk of human exposure to semi-volatile organic compounds (SVOCs) are based on the investigation of biological samples collected in an invasive or non-invasive manner. For SVOCs, which are typically introduced to humans through the respiratory system, dermal adsorption, or digestive system, sampling solutions generally used in the indoor environments are classified as...
-
APPLICATION OF THE THEORY OF SEMI-MARKOV PROCESSES TO DETERMINE A LIMITING DISTRIBUTION OF THE PROCESS OF CHANGES OF ABILITY AND INABILITY STATES OF FUEL SUPPLY SYSTEMS IN HEAVY FUEL DIESEL ENGINES
PublicationThe paper presents applicability of the theory of semi-Markov processes to determine a limiting distribution of the process of changes of technical states of fuel systems for marine engines running on heavy fuel oils. The proposed study of this process includes the components of such fuel systems like: 1 - injectors, 2 - high pressure hoses, 3 - injection pumps, 4 - low pressure hoses, 5 – fine filters, 6 - coarse filters, 7 – fuel-feed...
-
An efficient approach to optimization of semi‐stable routing in multicommodity flow networks
Publication -
Detonations in hydrogen-methane-air mixtures in semi confined flat channels
Publication -
Characteristics of Superconducting State in Vanadium: the Eliashberg Equations and Semi-analytical Formulas
Publication -
The challenge of abandonment for the sustainable management of Palaearctic natural and semi-natural grasslands
Publication -
Semi-Markovian models of the process of technical state changes of technical objects.
PublicationNajistotniejszym problemem eksploatacji wszystkich obiektów technicznych (urządzeń) jest problem racjonalnego (a zwłaszcza optymalnego) decyzyjnego sterowania procesem zmian stanów technicznych tych obiektów. Sterowanie takie może być realizowane w przypadku zastosowania między innymi modelu wspomnianego procesu zmian stanów. Mając to na uwadze, w opracowaniu tym przedstawiono formalny opis procesu eksploatacji obiektów technicznych...
-
Capturing semantics of semi-structured data using partial-order trees
PublicationW artykule zaprezentowano nowe podejście do problemu klasyfikacji danych semistrukturalnych. Kryteria klasyfikacji bazują na strukturze danych (zwanej typem danych) oraz na ich usytuowaniu w grafir danych (zwanym rolą danych). Zastosowano model OEM (Object Exchange Model) do reprezentacji nazy danych semistrukturalnych. Bazując na tej reprezentacji, definiuje się typy i role obiektów semistrukturalnych i organizuje się je w struktury...
-
A note on fast approximate backbone coloring of split graphs with star--like backbones
PublicationDla 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.
-
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.
-
Application of theory of semi-Markov processes to determining distribution of probabilistic process of marine accidents resulting from colission of ships
PublicationIn this paper is presented possible application of the theory of semi-Markov processes to elaborating an eight-state model of the process of occurrence of serviceability state and unserviceability states of sea-going ships making critical manoeuvres during their entering and leaving the ports. In the analysis it was taken into account that sea-going ships are in service for a very long time t (t → ∞). The model was elaborated to...
-
Możliwość oszacowania niezawodności silników o zapłonie samoczynnym z zastosowaniem teorii procesów semi-Markowa oraz podejmowania decyzji eksploatacyjnych z uwzględnieniem wiarygodności diagnozy o stanie technicznym tego rodzaju silników spalinowych = Possibility of estimating the reliability of diesel engines by applying the theory of semi-Markov processes and making operational decisions by considering reliability of diagnosis on technical state of this sort of combustion engines/
PublicationThe paper presents semi-Markov models of technical state transitions for diesel engines, useful for determining reliability of the engines. A possibility of application of a three-state model with a simplified matrix function, or even a two-state model, to determine reliability of the engines, has been described herein on examples of known from literature semi-Markov models, for the case when appropriate diagnosing systems (SDG)...
-
Amplitude-distance spectroscopy in semi-contact mode
Open Research DataSince it was invented by Binnig et al. in 1986, atomic force microscopy (AFM) plays a key role in science and technology at the nanoscale. AFM is a microscopic technique that visualizes the surface topography using the attractive and repulsive forces of interaction between several atoms (in theory) of a blade attached to the end of the probe lever and...