Filters
total: 1217
filtered: 869
Search results for: VERTEX 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.
-
Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph
PublicationA vertex cover of a graph G = (V, E) is a set X ⊂ V such that each edge of G is incident to at least one vertex of X. The ve cardinality of a vertex cover of G. A dominating set D ⊆ V is a weakly connected dominating set of G if the subgraph G[D]w = (N[D], Ew) weakly induced by D, is connected, where Ew is the set of all edges having at least one vertex in D. The weakly connected domination number γw(G) of G is the minimum cardinality...
-
INFLUENCE OF A VERTEX REMOVING ON THE CONNECTED DOMINATION NUMBER – APPLICATION TO AD-HOC WIRELESS NETWORKS
PublicationA minimum connected dominating set (MCDS) can be used as virtual backbone in ad-hoc wireless networks for efficient routing and broadcasting tasks. To find the MCDS is an NP- complete problem even in unit disk graphs. Many suboptimal algorithms are reported in the literature to find the MCDS using local information instead to use global network knowledge, achieving an important reduction in complexity. Since a wireless network...
-
Dynamic interaction of the cavitating propeller tip vortex with the rudder
PublicationPraca przedstawia model teoretyczny i obliczeniowy dynamicznego oddziaływania kawitującego wiru wierzchołkowego śruby okrętowej z płetwą sterową. W wyniku oddziaływania zmienia się geometria wiru, powodując generowanie wysokich pulsacji ciśnienia w otaczającej wodzie i na kadłubie okrętu. Wyniki obliczeń skonfrontowano z rezultatami pomiarów laboratoryjnych na modelach. Pokazano praktyczną przydatność modelu obliczeniowego do projektowania...
-
Simple design criteria and efficiency of hydrodynamic vortex separators
PublicationVortex separators are locally applied for waste water treatment in different systems - from storm waste water sewerage to water treatment in fish ponds. However, the methods for separator design presented in the literature are questionable. The paper presents two simple and functional criteria that were employed to construct a laboratory test stand. The test results gave positive feed back on the efficiency of vortex separators.
-
Free-surface elevation in open vortex flow controls
PublicationRotational form of fluid motion is complex, but very important in science and technology. The paper is devoted to the hydraulic mechanism of flow in open vortex flow controls, or regulators. The velocity field was described by the kinematic model, and intensity of rotation - by means of the energy balance between the input and dissipation. In consequence some algebraic expresions were obtained, which can be useful in approximated...
-
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.
-
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.
-
The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
PublicationGiven 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
PublicationIn 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...
-
Some results concerning the complexity of restricted colorings of graphs
Publication -
A note on compact and compact circular edge-colorings of graphs
PublicationW pracy rozważamy dwa warianty kolorowania krawędzi grafów prostych i ważonych, mianowicie kolorowania zwarte oraz zwarte cyrkularne. Rozważamy relacje pomiędzy nimi. Dowodzimy, że każdy zewnętrznie planarny graf dwudzielny posiada zwarte pokolorowanie krawędziowe oraz, że problem ten dla grafów ogólnych jest NP-zupełny. Podajemy również wielomianowy 1.5-przybliżony algorytm oraz pseudowielomianowy dokładny algorytm zwartego cyrkularnego...
-
Numerical prediction of steady and unsteady tip vortex cavitation on hydrofoils
PublicationArtykuł przedstawia metodę numeryczną do wyznaczania kawitujących wirów wierzchołkowych powstających za płatami nośnymi. Metoda ta jest oparta na rozwiązywanie dwufazowego turbulentnego przepływu cieczy lepkiej. Pozwala ona wyznaczyć geometrię kawitującego wiru dla różnych geometrii płata nośnego i dla różnych parametrów przepływu. Pokazano porównanie wyników obliczeń z pomiarami i rejestracjami wykonanymi na modelu płata w tunelu...
-
Measurements of heat transfer enhanced by the use of transverse vortex generators
PublicationArtykuł dotyczy badań eksperymentalnych intensyfikacji wymiany ciepła w modelowym wymienniku ciepła z turbulizatorami przepływu dla różnej geometrii turbulizatorów. W badaniach zastosowano termografię ciekłokrystaliczną i cyfrową anemometrię obrazową.
-
Measurements of heat transfer enhanced by the use of transverse vortex generators
PublicationArtykuł dotyczy badań eksperymentalnych wymiany ciepła w modelowym wymienniku ciepła z turbulizatorami przepływu dla różnej geometrii turbulizatorów. Badania wykonano przy użyciu termografii ciekłokrystalicznej i cyfrowej anemometrii obrazowej.
-
Experimental and numerical analysis of streamwise vortex generator for subsonic flow
PublicationW pracy przedstawiono porównanie wyników obliczeń numerycznych dwoma kodami (FLUENT i SPARC) na tle badań eksperymentalnych generatora wirów wzdłużnych. Przedstawiono wyniki dla liczb Macha przepływu głównego 0.3 i 0.8. Porównano ciśnienie całkowite w dwóch przekrojach za otworem przez który realizowany jest wydmuch. Przedstawiono strukturę wiru wzdłużnego uzyskaną dla obu programów. Średnica otworu jetu jest równa 1mm, co odpowiada...
-
Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number
PublicationGiven two types of graph theoretical parameters ρ and σ, we say that a graph G is (σ, ρ)- perfect if σ(H) = ρ(H) for every non-trivial connected induced subgraph H of G. In this work we characterize (γw, τ )-perfect graphs, (γw, α′)-perfect graphs, and (α′, τ )-perfect graphs, where γw(G), τ (G) and α′(G) denote the weakly connected domination number, the vertex cover number and the matching number of G, respectively. Moreover,...
-
Equitable colorings of some variation of corona products of cubic graphs
PublicationThe problem of determining the value of equitable chromatic number for multicoronas of cubic graphs is studied. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use almost optimal number of colors in the remaining cases.
-
No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs
PublicationIn the open shop scheduling with bioperational jobs each job consists of two unit operations with a delay between the end of the first operation and the beginning of the second one. No-wait requirement enforces that the delay between operations is equal to 0. No-idle means that there is no idle time on any machine. We model this problem by the interval incidentor (1, 1)-coloring (IIR(1, 1)-coloring) of a graph with the minimum...
-
Vortex flow caused by periodic and aperiodic sound in a relaxing maxwell fluid
PublicationThis paper concerns the description of vortex flow generated by periodic and aperiodic sound in relaxing Maxwell fluid. The analysis is based on governing equation of vorticity mode, which is a result of decomposition of the hydrodynamic equations for fluid flow with relaxation and thermal conductivity into acoustical and non-acoustical parts. The equation governing vorticity mode uses only instantaneous, not averaged over sound...
-
Magnetoelectric Vortex Magnetic Field Sensors Based on the Metglas/PZT Laminates
Publication -
APPLICATION OF VORTEX FLOW MODEL IN PROPELLER-STATOR SYSTEM DESIGN AND ANALYSIS
PublicationThe paper covers basics of the vortex model used for propeller-stator systems. The outline of the design algorithm is given and the results of its application are shown. The designed propeller-stator system was the subject of model tests run at the CTO model basin and cavitation tunnel. Stator’s influence on the delivered power required by the propeller and its revolution rate has been examined by conducting self-propulsion...
-
The new concept of product. Cooling band
PublicationThe chapter below presents the innovative solution consist in applying the cooling band to help holding the hot object. The solution was found through substitute inputs analysis and brain storm method. The new product was submitted in Polish Patent Office under the No. W.120905.
-
Realizacja algorytmów szyfrowania symetrycznego w układach FPGA Xilinx Virtex II.
PublicationW pracy zaprezentowano realizację algorytmów szyfrowania symetrycznego w układach FPGA firmy Xilinx z najnowszej rodziny Virtex II. Podkreślono zalety użycia układów programowalnych w systemach kryptograficznych w stosunku do układów ASIC oraz rozwiązań programowych. Przedstawiono struktury szyfrów blokowych Rijndael, Serpent i Twofish oraz moduły składowe i sposób ich realizacji w układach FPGA. Porównano architektury przetwarzania...
-
Vortex cavitation as a source of high level acoustic pressure generated by ship propellers
PublicationPraca przedstawia wyniki badań teoretycznych i eksperymentalnych nad mechanizmami fizycznymi generowania wysokiego ciśnienia akustycznego przez kawitujące wiry wierzchołkowe powstające na śrubach okrętowych
-
Experimental analysis on the risk of vortex ventilation and the free surface ventilation of marine propellers
Publication -
Investigations of vortex structures in granular materials under earth pressure conditions by DEM
PublicationW artykule pokazano rozwój wirów na poziomie ziarna materiału granulowanego podczas parcia pasywnego piasku na sztywną ściankę przemieszczającą się poziomo. Obliczenia wykonano stosując metodę DEM. Przyjęto 3 różne sposoby wyznaczenia wirów i ich czestotliwości.
-
An interval estimator for chlorine monitoring in drinking water distribution systems under uncertain system dynamics, inputs and chlorine concentration measurement errors
PublicationThe design of an interval observer for estimation of unmeasured state variables with application to drinking water distribution systems is described. In particular, the design process of such an observer is considered for estimation of the water quality described by the concentration of free chlorine. The interval observer is derived to produce the robust interval bounds on the estimated water quality state variables. The stability...
-
EXPERIMENTAL AND NUMERICAL VALIDATION OF THE IMPROVED VORTEX METHOD APPLIED TO CP745 MARINE PROPELLER MODEL
PublicationThe article presents a numerical analysis of the CP745 marine propeller model by means of the improved vortex method and CFD simulations. Both numerical approaches are validated experimentally by comparing with open water characteristics of the propeller. The introduced modification of the vortex method couples the lifting surface approach for the propeller blades and the boundary element method for the hub. What is more, a...
-
Non-disjoint Decomposition Using r-admissibility and Graph Coloring and Its Application in Index Generation Functions Minimization
Publication -
The aluminium and polycarbonate covering of the canopy above the stadium in Gdansk
PublicationW artykule przestawiono informacje o elementach konstrukcyjnych poszycia zadaszenia stadionu piłkarskiego w Gdańsku zrealizowanego z okazji rozgrywanych w Polsce i Ukrainie mistrzostw Europy w piłce nożnej. Omówione zostały elementy poszycia z poliwęglanu wraz z jego konstrukcją nośną oraz układem odwodnienia. Podano informacje o testach i badaniach przeprowadzonych przed wykonaniem obiektu, które zadecydowały o przyjętych rozwiązaniach...
-
Investigation of electrocatalytic gas sensor properties in presence of chlorine
PublicationProperties of sensor based on Nasicon with two round shaped platinum electrodes are investigated. Influence of different chlorine concentrations on the sensor response is presented. Measurements in different temperatures have been performed in order to determine optimal sensor working temperature.
-
Investigation of electrocatalytic gas sensor properties in presence of chlorine
PublicationIn this paper performance of an electrocatalytic sensor in presence of chlorine is investigated. Presented studies concern sensor prepared in ceramic technology based on NASICON as a solid electrolyte with two round shaped platinum electrodes. Measurements in different temperatures have been performed in order to determine optimal sensor working temperature.
-
The aluminium and polycarbonate covering to the roof over the stadium in Gdańsk
PublicationThis paper presents information about structural elements of the roof covering to the stadium in Gdansk built for the 2012 European Football Championship in Poland and the Ukraine. The paper discusses elements of the polycarbonate covering, the supporting structure and the drainage system. It also provides information about tests and research performed prior to construction, which determined the solutions adopted as well as...
-
Some aspects surface cooling by impinging jet
PublicationW pracy przedstawiono wyniki badań wymiany ciepła, uskoku hydraulicznego i stabilności podczas napływu strugi na powierzchnię ciała stałego.
-
Performance of a hybrid microjet – microchannel cooling module
PublicationThe paper presents the experimental investigation of a microjet- microchannel cooling module. In which microjets of water are impinging into the microchannels and forming a liquid film on the impingement surface. Applied technology takes benefits from two very attractive heat removal techniques. When lminar jets are impinging on the surface have a very high kinetic energy at the stagnation point, also in microchannels boundary...
-
New generation cooling systems for car engines
PublicationNormy czystości spalin silników samochodowych wymusiły rozwój elektronicznego sterowania pracą silników samochodowych. Do niedawna układy chłodzenia były bardzo tradycyjnymi - niesterowanymi programowo. W artykule przedstawiono możliwości wprowadzenia zaawansowanego sterowania mikroprocesorowego do układów chłodzenia silników spalinowych. Rozważania zilustrowano badaniami z literatury i własnymi pomiarami autora.
-
Cooling of electronic equipment by means of jets and microjets
PublicationW pracy przedstawiono rozwiązanie sprzężonej wymiany ciepła od uderzającej strugi cieczy oraz przewodzenia ciepła w łytce. Uzyskano proste zależności opisujące rozkład temperatur na płytce. Umożliwia to przeprowadzenie analizy wpływu różnych parametró na wymianę ciepła podczas chłodzenia urządzeń elektronicznych generujących ciepło.
-
Advanced Macromodel Matrix Structure Cloning for FDTD
PublicationWe propose an improved macromodel-based techniquefor efficient analysis of the structures based on PhotonicCrystals (PhC). The technique involves a new structure of thecoupling matrix and advanced cloning of not only the macromodel matrices, but also the coupling matrices SE and SH.The method allows one to shorten considerably the preprocessingtime, the RAM usage and also the iterating speed of performingFDTD. With this...
-
Structural optimization of microjet array cooling system
PublicationThe single phase heat transfer from an upward facing, horizontal copper surface to arrays of impinging water jets was experimentally investigated. Experimental configuration allows for a free-surface unconfined jets flow. Square nozzles 50 × 100 μm arranged in four different geometries were used. Additionally, for the set of two jets array geometry was varied by adjusting the nozzle to nozzle distance. The area averaged heat transfer...
-
Modeling of the internal combustion engine cooling system
PublicationThe article concerns computer modelling of processes in cooling systems of internal combustion engines. Modelling objectives and existing commercial programs are presented. It also describes Author’s own method of binding graphs used to describe phenomena in the cooling system of a spark ignition engine. The own model has been verified by tests on the engine dynamometer. An example of using a commercial program for experimental...
-
Development trends of automotive engine cooling systems
PublicationDzięki daleko idącym modyfikacjom układów zasilania i zapłonu silników samochodowych oraz udoskonaleniom układów oczyszczania spalin uzyskano znaczne zmniejszenie emisji związków toksycznych. Układy chłodzenia z pompą cieczy napędzaną mechanicznie stają się archaiczne nie pozwalając na swobodne sterowanie obiegiem cieczy. Również różna wartość temperatury potrzebnej do schładzania różnych procesów wymaga sterowanych zaworów trójdrożnych...
-
Investigations of vortex-structures in granular bodies based on DEM and Helmholtz-Hodge flow field decomposition
PublicationArtykuł omawia wyniki numeryczne dotyczące struktur wirowych w materiałach granulowanych. Obliczenia wykonano dla stanu pasywnego przemieszczającej się sztywnej ścianki. W symulacjach wykorzystano metodę elementów dyskretnych i dekompozycję Helmholtza/Hodge’a pola prędkości. Struktury wirowe okazały się znakomitym prekursorem lokalizacji odkształceń stycznych w materiałach granulowanych.
-
The selected roof covering technologies in the aspect of their life cycle costs
PublicationIn the article is presented an analysis of the life cycle costs calculation for selected roof coverings. The scope of research includes costs of construction, maintenance and demolition of the roof covering structure for two alternative technologies – the traditional and new generation. On the presented example of an industrial building with a roof area of 1000 m², the above costs are taken to consideration for the roof covering...
-
The saga of a fish: from a survival guide to closing lemmas
PublicationIn the paper by D. Burago, S. Ivanov and A. Novikov, “A survival guide for feeble fish”, it has been shown that a fish with limited velocity can reach any point in the (possibly unbounded) ocean provided that the fluid velocity field is incompressible, bounded and has vanishing mean drift. This result extends some known global controllability theorems though being substantially nonconstructive. We give a fish a different recipe...
-
Experimental and theoretical investigation of microjet cooling in metalurgical applications
PublicationW pracy zaprezentowano model wrzącej strugi uderzającej o powierzchnię i wytwarzającej cienki film cieczowy, w którym tworzą się pęcherzyki pary.
-
The automation of test stand for engine cooling system testing
PublicationW rozdziale przedstawiono budowę stanowiska do badań układu chłodzenia silnika samochodowego typu M111920. Układ był wyposażony w obwód podgrzewania paliwa gazowego i układ akumulacji ciepła. Stanowisko wyposażono w liczne termopary do pomiaru temperatur płynów i części metalowych silnika. Ważnym opracowanym zagadnieniem było rejestrowanie wielu pomiarów w czasie rzeczywistym, do czego użyto sieci transmisji danych CAN.
-
An advanced Thermal-FSI approach to flow heating/cooling
PublicationActually, two-way thermal-energy exchange between working fluid and solid material of a casing is a leading problem for modern – semi automatic – design techniques. Many questions should be solved, especially, the turbulent mode of thermal energy transport both in fluid and solid, should be re-examined and reformulated from the primary principles. In the present paper, a group of researchers from Energy Conversion Department of...