Search
Search results for: INTERVAL EDGE COLORING
-
Cops, a fast robber and defensive domination on interval graphs
PublicationThe game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...
-
Influence of edge subdivision on the convex domination number
PublicationWe study the influence of edge subdivision on the convex domination number. We show that in general an edge subdivision can arbitrarily increase and arbitrarily decrease the convex domination number. We also find some bounds for unicyclic graphs and we investigate graphs G for which the convex domination number changes after subdivision of any edge in G.
-
Bounds on the vertex-edge domination number of a tree
PublicationA vertex-edge dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every edge of $G$ is incident with a vertex of $D$ or a vertex adjacent to a vertex of $D$. The vertex-edge domination number of a graph $G$, denoted by $\gamma_{ve}(T)$, is the minimum cardinality of a vertex-edge dominating set of $G$. We prove that for every tree $T$ of order $n \ge 3$ with $l$ leaves and $s$ support vertices we have $(n-l-s+3)/4...
-
Parallel immune system for graph coloring
PublicationThis paper presents a parallel artificial immune system designed forgraph coloring. The algorithm is based on the clonal selection principle. Each processor operates on its own pool of antibodies and amigration mechanism is used to allow processors to exchange information. Experimental results show that migration improves the performance of the algorithm. The experiments were performed using a high performance cluster on a set...
-
Equitable coloring of corona products of graphs
PublicationIn this paper we consider an equitable coloring of some corona products of graphs G and H in symbols, G o H). In particular, we show that deciding the colorability of G o H is NP-complete even if G is 4-regular and H is K_2. Next, we prove exact values or upper bounds on the equitable chromatic number of G o H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a path, a cycle or a complete graph.
-
Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationIn 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
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.
-
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...
-
Generic invariant measures for iterated systems of interval homeomorphisms
PublicationIt is well known that iterated function systems generated by orientation preserving homeomorphisms of the unit interval with positive Lyapunov exponents at its ends admit a unique invariant measure on (0, 1) provided their action is minimal. With the additional requirement of continuous differentiability of maps on a fixed neighbourhood of {0,1} { 0 , 1 } , we present a metric in the space of such systems which renders it complete....
-
Tight bounds on global edge and complete alliances in trees
PublicationIn the talk the authors present some tight upper bounds on global edge alliance number and global complete alliance number of trees. Moreover, we present our NP-completeness results from [8] for global edge alliances and global complete alliances on subcubic bipartite graphs without pendant vertices. We discuss also polynomial time exact algorithms for finding the minimum global edge alliance on trees [7] and complete alliance...
-
A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4
PublicationIn 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:...
-
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...
-
Permanent traffic counting stations - Expressway S6 in Gdansk (dataset containing 5-min aggregated traffic data and weather information)
Open Research DataThe data includes traffic data from permanent traffic count station located on the expressway S6 in the Tri-City Agglomeration area in Poland. The data covers the three year period between 2014 and 2017 and one direction of traffic (southbound).
-
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationWe 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.
-
Edge and Pair Queries-Random Graphs and Complexity
PublicationWe investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random graphs, and showing that determining any of the two parameters is NP-hard for bounded degree graphs.
-
Comparison of edge detection algorithms for electric wire recognition
PublicationEdge detection is the preliminary step in image processing for object detection and recognition procedure. It allows to remove useless information and reduce amount of data before further analysis. The paper contains the comparison of edge detection algorithms optimized for detection of horizontal edges. For comparison purposes the algorithms were implemented in the developed application dedicated to detection of electric line...
-
A method of Functional Test interval selection with regards to Machinery and Economical aspects
PublicationThis paper discusses the problem of choosing the optimal frequency of functional test, including the reliability calculations and production efficiency, but also the effect of company risk management. The proof test as a part of the functional test interval is well described for the process industry. Unfortunately, this situation is not the case for the machinery safety functions with low demand mode. Afterwards, it is presented...
-
Badanie jakości transmisji w podsystemie EDGE.
PublicationPrzedstawiono wyniki badań symulacyjnych jakości transmisji w podsystemie EDGE, będącego rozwinięciem systemu GSM w kierunku systemu trzeciej generacji. Uzyskane wyniki odnoszą się do szybkiej transmisji danych, realizowanej w oparciu o komutację kanałów ECSD oraz komutację pakietów EGPRS dla wybranych środowisk propagacyjnych.
-
Monitoring of Chlorine Concentration in Drinking Water Distribution Systems Using an Interval Estimator
PublicationThis paper describes the design of an interval observer for the estimation of unmeasured quality state variables in drinking water distribution systems. The estimator utilizes a set bounded model of uncertainty to produce robust interval bounds on the estimated state variables of the water quality. The bounds are generated by solving two differential equations. Hence the numerical efficiency is sufficient for on-line monitoring...
-
Big Data and the Internet of Things in Edge Computing for Smart City
PublicationRequests expressing collective human expectations and outcomes from city service tasks can be partially satisfied by processing Big Data provided to a city cloud via the Internet of Things. To improve the efficiency of the city clouds an edge computing has been introduced regarding Big Data mining. This intelligent and efficient distributed system can be developed for citizens that are supposed to be informed and educated by the...
-
On the approximation of the UWB dipole elliptical arms with stepped-edge polygon
PublicationA simple method of approximation of the ellipticalpatch with stepped-edge polygon is proposed as an introductionto wider studies over the planar ultrawideband (UWB) antennas.The general idea is to replace the elliptical patch with an equivalentpolygonal patch, with minimum loss in the performance. Theprinciples of the proposed method are presented in this letter, aswell as the results of performed numerical studies and its experimentalverification....
-
A Method and Device for 3D Recognition of Cutting Edge Micro Geometry
PublicationA very useful method was successfully applied in the investigation of tools for machining wood and wood based composites. It allows scanning of the cutting edge micro geometry in three dimensions and reproducing it in a virtual space as a 3D surface. The application of the method opens new possibilities of studying tool wear by scanning, including the calculation of volume loss and other analysis of tool wedge geometry along and...
-
Edge-Computing based Secure E-learning Platforms
PublicationImplementation of Information and Communication Technologies (ICT) in E-Learning environments have brought up dramatic changes in the current educational sector. Distance learning, online learning, and networked learning are few examples that promote educational interaction between students, lecturers and learning communities. Although being an efficient form of real learning resource, online electronic resources are subject to...
-
The Method of Selecting the Interval of Functional Tests Taking into Account Economic Aspects and Legal Requirements
PublicationThe article discusses the problem of choosing the optimal frequency of functional tests, taking into account the reliability and law requirements, but also the impact of business aspects in the company. The subject of functional test interval is well described for purposes of the process industry. Unfortunately, this is not the case for the machinery safety functions with low demand mode. This is followed by a presentation of the...
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublicationIn 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...
-
Computer experiments with a parallel clonal selection algorithm for the graph coloring problem
PublicationArtificial 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...
-
Tuning the work function of graphite nanoparticles via edge termination
PublicationGraphite nanoparticles are important in energy materials applications such as lithium-ion batteries (LIBs), supercapacitors and as catalyst supports. Tuning the work function of the nanoparticles allows local control of lithiation behaviour in LIBs, and the potential of zero charge of electrocatalysts and supercapacitors. Using large scale density functional theory (DFT) calculations, we find that the surface termination of multilayer...
-
Edge-Guided Mode Performance and Applications in Nonreciprocal Millimeter-Wave Gyroelectric Components
PublicationThe analogies between the behavior of gyromagnetic and gyroelectric nonreciprocal structures, the use of the simple transfer matrix approach, and the edge-guided (EG) wave property, supported in a parallel plate model for integrated magnetized semiconductor waveguide, are investigated in those frequency regions, where the effective permittivity is negative or positive. As with their ferrite counterparts, the leakage of the EG waves...
-
An O ( n log n ) algorithm for finding edge span of cacti
PublicationLet G=(V,E) be a nonempty graph and xi be a function. In the paper we study the computational complexity of the problem of finding vertex colorings c of G such that: (1) |c(u)-c(v)|>=xi(uv) for each edge uv of E; (2) the edge span of c, i.e. max{|c(u)-c(v)|: uv belongs to E}, is minimal. We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for...
-
The edge of the [dis]order
Publication -
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...
-
Some Artificial Intelligence Driven Algorithms For Mobile Edge Computing in Smart City
PublicationSmart mobile devices can share computing workload with the computer cloud that is important when artificial intelligence tools support computer systems in a smart city. This concept brings computing on the edge of the cloud, closer to citizens and it can shorten latency. Edge computing removes a crucial drawback of the smart city computing because city services are usually far away from citizens, physically. Besides, we introduced...
-
Rank Coloring of Graphs.
PublicationRozdział jest poświęcony uporządkowanemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Harmonions Coloring of Graphs.
PublicationProblem 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.
PublicationNiniejszy 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.
PublicationRozdział 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.
PublicationRozdział jest poświęcony sumacyjnemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Interval estimator for chlorine monitoring in drinking water distribution systems under uncertain system dynamics, inputs and state measurement errors
PublicationThe design of interval observer for estimation of unmeasured state variables for application to drinking water distribution systems is described in this paper. In particular, it considers the design of such observer for estimation of water quality described by free chlorine concentration. An interval observer is derived to produce robust interval bounds on the estimated water quality state variables. The stability and robustness...
-
The maximum edge-disjoint paths problem in complete graphs
PublicationRozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...
-
Invariant Measures for Uncountable Random Interval Homeomorphisms
PublicationA necessary and sufficient condition for the iterated function system { f (·, ω) | ω ∈ } with probability P to have exactly one invariant measure μ∗ with μ∗((0, 1)) = 1 is given. The main novelty lies in the fact that we only require the transformations f (·, ω) to be increasing homeomorphims, without any smoothness condition, nei- ther we impose conditions on the cardinality of . In particular, positive Lyapunov exponents conditions...
-
Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks
PublicationWe introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal...
-
Rendezvous of heterogeneous mobile agents in edge-weighted networks
PublicationWe introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal...
-
POLDER AND CITY: SUSTAINING WATER LANDSCAPES ON AN URBAN EDGE
PublicationThe question investigated in this paper is how to maintain the environmental quality of the polder landscape encompassing the city in the condition of urban pressure on this landscape. On the basis of theoretical approaches, historical surveys and introductory study models new ideas are tested on the case study of Gdansk, a city located in the Vistula River delta in northern Poland. Research shows that the city was created as a...
-
Novel Analytic-Numerical Model of Free Convection: with Leading Edge Considered
PublicationA novel solution of the free convection boundary problem is represented in analytical form for velocity and temperature for an isothermal vertical plate, as an example. These fields are built as a Taylor Series in the x coordinate with coefficients as functions of the vertical coordinate (y). We restrict ourselves by cubic approximation for both functions. The basic Navier-Stokes and Fourier-Kirchhoff equations and boundary conditions...
-
Koala graph coloring library: an open graph coloring library for real-world applications
PublicationPomimo 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 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].
-
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.
-
Equitable vertex coloring of graphs
PublicationW 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.