Search
Filters
total: 857
-
Catalog
Search results for: RECTANGULAR GRID GRAPHS
-
On the super domination number of lexicographic product graphs
PublicationThe neighbourhood of a vertexvof a graphGis the setN(v) of all verticesadjacent tovinG. ForD⊆V(G) we defineD=V(G)\D. A setD⊆V(G) is called a super dominating set if for every vertexu∈D, there existsv∈Dsuch thatN(v)∩D={u}. The super domination number ofGis theminimum cardinality among all super dominating sets inG. In this article weobtain closed formulas and tight bounds for the super dominating number oflexicographic product...
-
A Point Set Connection Problem for Autonomous Mobile Robots in a Grid
PublicationConsider an orthogonal grid of streets and avenues in a Manhattan-like city populated by stationary sensor modules at some intersections and mobile robots that can serve as relays of information that the modules exchange, where both module-module and module-robot communication is limited to a straight line of sight within the grid. The robots are oblivious and move asynchronously. We present a distributed algorithm that, given...
-
Common Independence in Graphs
PublicationAbstract: The cardinality of a largest independent set of G, denoted by α(G), is called the independence number of G. The independent domination number i(G) of a graph G is the cardinality of a smallest independent dominating set of G. We introduce the concept of the common independence number of a graph G, denoted by αc(G), as the greatest integer r such that every vertex of G belongs to some independent subset X of VG with |X|...
-
A Review of Standards with Cybersecurity Requirements for Smart Grid
PublicationAssuring cybersecurity of the smart grid is indispensable for the reliable operation of this new form of the electricity network. Experts agree that standardised solutions and practices should be applied in the first place. In recent years many new standards for smart grids have been published, which paradoxically results in the difficulty of finding a relevant publication in this plethora of literature. This paper presents results...
-
Deterministic Rendezvous in Restricted Graphs
PublicationIn this paper we consider the problem of synchronous rendezvous in which two anonymous mobile entities (robots) A and B are expected to meet at the same time and point in a graph G = (V;E). Most of the work devoted to rendezvous in graphs assumes that robots have access to the same sets of nodes and edges, where the topology of connections may be initially known or unknown. In our work we assume the movement of robots is restricted...
-
Mersenne Number Finding and Collatz Hypothesis Verification in the Comcute Grid System
PublicationIn this chapter, some mathematic applications have been described to test scalability of the Comcute grid system. Especially, a verification of the Collatz hypothesis and finding Mersenne numbers were applied to prove the scalability and high performance of this grid system. Results were compared with outcomes obtained by the other grid systems.
-
Three-fast-searchable graphs
PublicationIn the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...
-
On bipartization of cubic graphs by removal of an independent set
PublicationWe study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set.
-
Chromatic cost coloring of weighted bipartite graphs
PublicationGiven a graph G and a sequence of color costs C, the Cost Coloring optimization problem consists in finding a coloring of G with the smallest total cost with respect to C. We present an analysis of this problem with respect to weighted bipartite graphs. We specify for which finite sequences of color costs the problem is NP-hard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended...
-
Internetowe systemy przetwarzania rozproszonego typu grid w zastosowaniach biznesowych
PublicationSkoncentrowano się na możliwościach wykorzystania oraz integracji rozproszonych mocy obliczeniowych komputerów Internautów w globalnej sieci www. Zaprezentowano paradygmaty sieciowego przetwarzania typu grid computing oraz volunteer computing. Podkreślono istotność tego typu przetwarzania w zagadnieniach wymagających bardzo dużych mocy obliczeniowych. Zaprezentowano przykłady rozwiązań systemowych tego typu: system BOINC, będący...
-
A Paradigm for HV, MV, LV Distribution Grid Development Planning
PublicationIn the literature, including that relating to businesses in the energy (and power) sector, the concept of these organizations’ operating paradigm may be found. The paper discusses the concept of the paradigm, with a focus on the power grid development planning paradigm. Against this background, issues related to energy security and power systems development trends and problems are presented. A new paradigm is proposed for distribution...
-
On Computational Aspects of Greedy Partitioning of Graphs
PublicationIn this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite...
-
Equitable coloring of corona multiproducts of graphs
PublicationWe 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.
-
Application of PL-Grid Platform for Modeling of the Selected Acoustic Phenomena
PublicationDomain grids are specific computational environments, developed within the PLGrid Plus project. For the Acoustic domain grid two supercomputer grid based services were prepared. Dedicated software consists of the outdoor sound propagation module and psychoacoustical noise dosimeter. The results are presented in a form of maps of sound level and Temporary Threshold Shift (TTS) values, therefore the services may play an informative...
-
The Backbone Coloring Problem for Small Graphs
PublicationIn 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...
-
Genetic Programming for Workload Balancing in the Comcute Grid System
PublicationA genetic programming paradigm is implemented for reliability optimization in the Comcute grid system design. Chromosomes are generated as the program functions and then genetic operators are applied for finding Pareto-suboptimal task assignment and scheduling. Results are compared with outcomes obtained by an adaptive evolutionary algorithm.
-
Block graphs with large paired domination multisubdivision number
PublicationThe paired domination multisubdivision number of a nonempty graph G, denoted by msdpr(G), is the smallest positive integer k such that there exists an edge which must be subdivided k times to increase the paired domination number of G. It is known that msdpr(G) ≤ 4 for all graphs G. We characterize block graphs with msdpr(G) = 4.
-
Graphs hard-to-process for greedy algorithm MIN
PublicationWe compare results of selected algorithms that approximate the independence number in terms of the quality of constructed solutions. Furthermore, we establish smallest hard- to-process graphs for the greedy algorithm MIN.
-
Estimation of the Maximum Permissible PV Power to be Connected to the MV Grid
PublicationIn recent decades, a significant increase in the share of renewable energy sources in power grids at various voltage levels has been observed. A number of articles have been published highlighting emerging problems in low-voltage grids with a large share of prosumers and in medium- and high-voltage grids to which photovoltaic (PV) plants are connected. The article analyzes the medium-voltage grid in terms of the possibility of...
-
Global defensive sets in graphs
PublicationIn the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if | N [ X ] ∩ S | ≥ | N [ X ] \ S | holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for...
-
Minimum order of graphs with given coloring parameters
PublicationA complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...
-
Non-isolating 2-bondage in graphs
PublicationA 2-dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. The non-isolating 2-bondage number of G, denoted by b_2'(G), is the minimum cardinality among all sets of edges E' subseteq E such that delta(G-E') >= 1 and gamma_2(G-E') > gamma_2(G)....
-
An Analysis of Probe-Fed Rectangular Patch Antennas With Multilayer and Multipatch Configurations on Cylindrical Surfaces
PublicationA multi-patch configuration of probe-fed rectangular microstrip antennas mounted on a cylindrical body, with electrically small radius, with an arbitrary number of substrate and superstrate layers is investigated in this paper. A full-wave analysis and a moment-method calculation are employed. A unified procedure for creating proper matrices for the investigated geometry of the structure is outlined here. Numerical results for...
-
Interval incidence coloring of subcubic graphs
PublicationIn 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.
-
Optymalizacja równoważenia obciążeń w systemach klasy grid
PublicationZaprezentowano techniki równoważenia obciążeń testowane w systemie rozproszonym Comcute o architekturze typu grid. Omówiono niezbędne uwarunkowania środowiska prowadzenia obliczeń w zestawie laboratoryjnym Politechniki Gdańskiej, a także odniesiono się do kryteriów kierunkujących równoważenie obciążeń. Przedstawiono wielopoziomową metodę równoważenia obciążeń.
-
On domination multisubdivision number of unicyclic graphs
PublicationThe paper continues the interesting study of the domination subdivision number and the domination multisubdivision number. On the basis of the constructive characterization of the trees with the domination subdivision number equal to 3 given in [H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009), 622–628], we constructively characterize all connected unicyclic graphs with...
-
On-line ranking of split graphs
PublicationA vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm...
-
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.
-
Power Electronic Transformer For Smart Grid Application
PublicationIn this paper the control system of Power Electronic Transformer (PET) for the Smart Grid application is proposed. The structure of PET is based on two Cascaded H-bridge (CHB) converters. The electrical energy is transferred between converters using Dual-Active-Bridges (DAB) and high-frequency transformers. This type of coupling has been used to connect the DC-links of all H-bridges. The proposed control system for PET makes it...
-
Foundations of Grid Processing Architecture for the Comcute System
PublicationFundamental system algorithms and structures implemented in the Comcute system are described and analysed in detail. Layered architecture of the system model is highlighted. System tasks of the layers are elaborated, presented and described. Operational details of communication interfaces among layers are worked out and examined. The focus is put onto implemented system components with regard to their operability and efficiency....
-
Domination subdivision and domination multisubdivision numbers of graphs
PublicationThe domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T)<=3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number...
-
Paired domination subdivision and multisubdivision numbers of graphs
PublicationThe paired domination subdivision number sdpr(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the paired domination number of G. We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the paired domination muttisubdivision number of a nonempty graph...
-
Frequently updated noise threat maps created with use of supercomputing grid
PublicationAn innovative supercomputing grid services devoted to noise threat evaluation were presented. The services described in this paper concern two issues, first is related to the noise mapping, while the second one focuses on assessment of the noise dose and its influence on the human hearing system. The discussed services were developed within the PL-Grid Plus Infrastructure which accumulates Polish academic supercomputer centers....
-
Graphs with isolation number equal to one third of the order
PublicationA set D of vertices of a graph G is isolating if the set of vertices not in D and with no neighbor in D is independent. The isolation number of G, denoted by \iota(G) , is the minimum cardinality of an isolating set of G. It is known that \iota(G) \leq n/3 , if G is a connected graph of order n, , distinct from C_5 . The main result of this work is the characterisation of unicyclic and block graphs of order n with isolating number...
-
An Overview of Bidirectional EV Chargers: Empowering Traction Grid-Powered Chargers
PublicationIn recent years, the number of electric vehicles has been at least doubling year after year. As a result, today electric vehicles already account for approximately 10% of the global automotive market, which positively affects environment in urbanized areas. However, to take full advantage of the EV integration it is necessary to use renewable sources for their charging; optimally place charging stations/terminals; optimally manage...
-
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.
-
Parity vertex colouring of graphs
PublicationA parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let Xp(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for...
-
Dobór elementów instalacji fotowoltaicznych - instalacje on-grid
PublicationObecnie instalacje fotowoltaiczne dołączone do sieci stanowią 72% wszystkich systemów fotowoltaicznych.System PV podłączony do sieci elektroenergetycznej wytwarza energię, która jest w sposób ciągły przekazywana do sieci, co (przeciwnie niż w instalacjach off-grid) pozwala na całkowite niedopasowanie liczby zamontowanych w instalacji modułów fotowoltaicznych do zapotrzebowania obiektu na energię elektryczną. W efekcie instalacja...
-
Image Processing Techniques for Distributed Grid Applications
PublicationParallel approaches to 2D and 3D convolution processing of series of images have been presented. A distributed, practically oriented, 2D spatial convolution scheme has been elaborated and extended into the temporal domain. Complexity of the scheme has been determined and analysed with respect to coefficients in convolution kernels. Possibilities of parallelisation of the convolution operations have been analysed and the results...
-
Use of AMI Meters in the Process of Low Voltage Grid Optimization
PublicationThis is a report of a project involving, inter alia, low voltage grid performance optimization with data from AMI meters . The study was supported with a European UPGRID grant, and executed by a consortium of companies from seven European countries, including Poland .
-
An Analysis of Elliptical-Rectangular Multipatch Structure on Dielectric-Coated Confocal and Nonconfocal Elliptic Cylinders
PublicationA rigorous analysis of the resonance frequency problem of an elliptical-rectangular microstrip structure mounted on dielectric-coated elliptic conducting cylinder, with electrically small radius, is investigated in this paper. A full-wave analysis and a moment-method calculation are employed. The analysis is carried out considering the expansion of the field as a series of Mathieu functions. The complex resonance frequencies of...
-
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”,...
-
SMART GRID TECHNOLOGIES IN ELECTRIC POWER SUPPLY SYSTEMS OF PUBLIC TRANSPORT
PublicationNowadays the issue of electric energy saving in public transport is becoming a key area of interest which is connected both with a growth in environmental awareness of the society and an increase in the prices of fuel and electricity. It can be achieved by improving the usage of regenerative breaking. In 2016 the Przedsiębiorstwo Komunikacji Trolejbusowej (PKT, Trolleybus Transport Company) in Gdynia began practical implementation...
-
Single-phase power electronics transformer with active functions for smart grid
PublicationThis paper presents the control of one cell of a modular single-phase power electronics transformer with active functions for meeting the smart grid concept. In this way, the converter could be used not only as a conventional transformer but also for grid such as reactive power, harmonic elimination and energy storage. The topology of the cell is composed by a bidirectional converter with three stages: a half bridge in the input...
-
Some Optimization Methods for Simulations in Volunteer and Grid Systems
PublicationIn this chapter, some optimization methods have been presented for improving performance of simulations in the volunteer and grid computing system called Comcute. Some issues related to the cloud computing can be solved by presented approaches as well as the Comcute platform can be used to simulate execution of expensive and energy consuming long-term tasks in the cloud environment. In particular, evolutionary algorithms as well...
-
The paired-domination and the upper paired-domination numbers of graphs
PublicationIn this paper we obtain the upper bound for the upper paired-domination number and we determine the extremal graphs achieving this bound. Moreover we determine the upper paired- domination number for cycles.
-
On the size of identifying codes in triangle-free graphs
PublicationIn an undirected graph G, a subset C⊆V(G) such that C is a dominating set of G, and each vertex in V(G) is dominated by a distinct subset of vertices from C, is called an identifying code of G. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph G, let gammaID(G) be the minimum cardinality of an identifying code in G. In this paper, we show that for any connected...
-
All graphs with paired-domination number two less than their order
PublicationLet G=(V,E) be a graph with no isolated vertices. A set S⊆V is a paired-dominating set of G if every vertex not in S is adjacent with some vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination number γp(G) of G is defined to be the minimum cardinality of a paired-dominating set of G. Let G be a graph of order n. In [Paired-domination in graphs, Networks 32 (1998), 199-206] Haynes and Slater...
-
Domination-Related Parameters in Rooted Product Graphs
PublicationAbstract A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those sets of vertices of a graph satisfying some domination property together with other conditions on the vertices of G. Here, we investigate several domination-related parameters in rooted product graphs.
-
Design of Frequency-Reconfigurable Branch-Line Crossover Using Rectangular Dielectric Channels
PublicationThis paper presents an efficient yet straightforward passive reconfiguration technique to tune the operating frequency of a branch-line crossover (BLCO). The underlying principle is to fill rectangular dielectric channels (RDCs) prepared beforehand with either air or materials of different relative permittivity. Two configurations (one RDC and three RDCs in each arm) of the branch-line crossover are employed to estimate the tunability...