Search
Filters
total: 1226
filtered: 1065
displaying 1000 best results Help
Search results for: INDEPENDENCE NUMBER, GREEDY ALGORITHM, GRAPH HARD-TO-PROCESS
-
Unicyclic graphs with equal total and total outer-connected domination numbers
PublicationLet G = (V,E) be a graph without an isolated vertex. A set D ⊆ V (G) is a total dominating set if D is dominating and the in- duced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total domi- nating set of G. A set D ⊆ V (G) is a total outer–connected dominating set if D is total dominating and the induced subgraph G[V (G)−D] is a connected graph. The total outer–connected...
-
Distributed graph searching with a sense of direction
PublicationIn this work we consider the edge searching problem for vertex-weighted graphs with arbitrarily fast and invisible fugitive. The weight function w provides for each vertex v the minimum number of searchers required to guard v, i.e., the fugitive may not pass through v without being detected only if at least w(v) searchers are present at v. This problem is a generalization of the classical edge searching problem, in which one has...
-
An upper bound for the double outer-independent domination number of a tree
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)\D is independent. The double outer-independent domination number of a graph G, denoted by γ_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We prove...
-
Numerically efficient algorithm for compact microwave device optimization with flexible sensitivity updating scheme
PublicationAn efficient trust-region algorithm with flexible sensitivity updating management scheme for electromagnetic (EM)-driven design optimization of compact microwave components is proposed. During the optimization process, updating of selected columns of the circuit response Jacobian is performed using a rank-one Broyden formula (BF) replacing finite differentiation (FD). The FD update is omitted for directions sufficiently well aligned...
-
Optimised Robust Placement of Hard Quality Sensors for Robust Monitoring of Quality in Drinking Water Distribution Systems
PublicationA problem of optimised robust placement of the hard quality sensors in Drinking Water Distribution Systems under several water demand scenarios for robust quality monitoring is formulated. Numerical algorithms to solve the problem are derived. The optimality is meant as achieving at the same time a desired trade off between the sensor capital and maintenance costs and resulting robust estimation accuracy of the monitoring algorithm...
-
The Backbone Coloring Problem for Bipartite Backbones
PublicationLet G be a simple graph, H be its spanning subgraph and λ≥2 be an integer. By a λ -backbone coloring of G with backbone H we mean any function c that assigns positive integers to vertices of G in such a way that |c(u)−c(v)|≥1 for each edge uv∈E(G) and |c(u)−c(v)|≥λ for each edge uv∈E(H) . The λ -backbone chromatic number BBCλ(G,H) is the smallest integer k such that there exists a λ -backbone coloring c of G with backbone H satisfying...
-
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublicationIn the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.
-
Isolation Number versus Domination Number of Trees
PublicationIf G=(VG,EG) is a graph of order n, we call S⊆VG an isolating set if the graph induced by VG−NG[S] contains no edges. The minimum cardinality of an isolating set of G is called the isolation number of G, and it is denoted by ι(G). It is known that ι(G)≤n3 and the bound is sharp. A subset S⊆VG is called dominating in G if NG[S]=VG. The minimum cardinality of a dominating set of G is the domination number, and it is denoted by γ(G)....
-
Novel structure and design of compact UWB slot antenna
PublicationIn this paper, a novel structure of a compact UWB slot antenna is presented along with a simulation-driven design optimization algorithm for adjusting geometry parameters of the device. Our primary objective is to obtain small footprint of the structure while maintaining its acceptable electrical performance. It is achieved by introducing sufficiently large number of geometry degrees of freedom, including increased number of parameterized...
-
JamesBot - an intelligent agent playing StarCraft II
PublicationThe most popular method for optimizing a certain strategy based on a reward is Reinforcement Learning (RL). Lately, a big challenge for this technique are computer games such as StarCraft II which is a real-time strategy game, created by Blizzard. The main idea of this game is to fight between agents and control objects on the battlefield in order to defeat the enemy. This work concerns creating an autonomous bot using reinforced...
-
Weakly connected Roman domination in graphs
PublicationA Roman dominating function on a graph G=(V,E) is defined to be a function f :V → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v)=2. A dominating set D⊆V is a weakly connected dominating set of G if the graph (V,E∩(D×V)) is connected. We define a weakly connected Roman dominating function on a graph G to be a Roman dominating function such that the set...
-
A note on total reinforcement in graphs
PublicationIn this note we prove a conjecture and inprove some results presendet in a recent paper of N. Sridharan, M.D. Elias, V.S.A. Subramanian, Total reinforcement number of a graph, AKCE Int. J. Graphs Comb. 4 (2) (2007) 197-202.
-
A construction for the hat problem on a directed graph
PublicationA team of n players plays the following game. After a strategy session, each player is randomly fitted with a blue or red hat. Then, without further communication, everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. Visibility is defined by a directed graph; that is, vertices correspond to players, and a player can see each player to whom he is connected by an arc. The...
-
Bio-Based Polyurethane Composites and Hybrid Composites Containing a New Type of Bio-Polyol and Addition of Natural and Synthetic Fibers
PublicationThis article describes how new bio-based polyol during the liquefaction process can be obtained. Selected polyol was tested in the production of polyurethane resins. Moreover, this research describes the process of manufacturing polyurethane materials and the impact of two different types of fibers—synthetic and natural (glass and sisal fibers)—on the properties of composites. The best properties were achieved at a reaction temperature...
-
MICROSEISMIC EVENT DETECTION USING DIFFERENT ALGORITHMS ON REAL DATA FROM PATCH ARRAY GEOPHONE GRID FROM EASTERN POMERANIA FRACTURING JOB
PublicationThe microseismic monitoring is a method of monitoring of fracture propagation during hydraulic fracturing process. Hydraulic fracturing is a method of reservoir stimulation used especially for unconventional gas recovery. A matrix of several thousand geophones is placed on the surface of earth to record every little tremor of ground induced by fracturing process. Afterwards, the signal is analysed and the place of tremor occurrence...
-
Towards Emotion Acquisition in IT Usability Evaluation Context
PublicationThe paper concerns extension of IT usability studies with automatic analysis of the emotional state of a user. Affect recognition methods and emotion representation models are reviewed and evaluated for applicability in usability testing procedures. Accuracy of emotion recognition, susceptibility to disturbances, independence on human will and interference with usability testing procedures are...
-
Preparation and some properties of multiblock copoly(amide-b-amide)s
PublicationThe paper concerns the polymers built of oligoamide hard blocks and oligoamide soft blocks (KPAA, formula I). Oligo(laurolactam) (PA12) was used as hard block and the product of reaction of dimerized fatty acid and hexamethylene diamine (PA6,36) was used as a soft one. Effects of molar ratio of these blocks on the following properties of KPAA have been investigated: limiting viscosity number ([2]), degrees of swelling in water...
-
A lower bound on the double outer-independent domination number of a tree
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)D is independent. The double outer-independent domination number of a graph G, denoted by gamma_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We...
-
Liczby Ramseya on-line dla różnych klas grafów
PublicationRozpatrujemy grę rozgrywaną na nieskończonej liczbie wierzchołków, w której każda runda polega na wskazaniu krawędzi przez jednego gracza - Budowniczego oraz pokolorowaniu jej przez drugiego gracza - Malarkę na jeden z dwóch kolorów, czerwony lub niebieski. Celem Budowniczego jest zmuszenie Malarki do stworzenia monochromatycznej kopii wcześniej ustalonego grafu H w jak najmniejszej możliwej liczbie ruchów. Zakładamy, że gracze...
-
Implementation of discrete convolution using polynomial residue representation
PublicationConvolution is one of the main algorithms performed in the digital signal processing. The algorithm is similar to polynomial multiplication and very intensive computationally. This paper presents a new convolution algorithm based on the Polynomial Residue Number System (PRNS). The use of the PRNS allows to decompose the computation problem and thereby reduce the number of multiplications. The algorithm has been implemented in Xilinx...
-
A lower bound on the total outer-independent domination number of a tree
PublicationA total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V(G)D is independent. The total outer-independent domination number of a graph G, denoted by gamma_t^{oi}(G), is the minimum cardinality of a total outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_t^{oi}(T) >= (2n-2l+2)/3,...
-
An algorithm for enhancing macromodeling in finite element analysis of waveguide components
PublicationAn algorithm for enhancing the finite element method with local model order reduction is presented. The proposed technique can be used in fast frequency domain simulation of waveguide components and resonators. The local reduction process applied to cylindrical subregions is preceded by compression of the number of variables on its boundary. As a result,the finite element large system is converted into a very compact set of linear...
-
Eventual Convergence of the Reputation-Based Algorithm in IoT Sensor Networks
PublicationUncertainty in dense heterogeneous IoT sensor networks can be decreased by applying reputation-inspired algorithms, such as the EWMA (Exponentially Weighted Moving Average) algorithm, which is widely used in social networks. Despite its popularity, the eventual convergence of this algorithm for the purpose of IoT networks has not been widely studied, and results of simulations are often taken in lieu of the more rigorous proof....
-
A NOTE ON ON-LINE RAMSEY NUMBERS FOR QUADRILATERALS
PublicationWe consider on-line Ramsey numbers defined by a game played between two players, Builder and Painter. In each round Builder draws an the edge and Painter colors it either red or blue, as it appears. Builder’s goal is to force Painter to create a monochromatic copy of a fixed graph H in as few rounds as possible. The minimum number of rounds (assuming both players play perfectly) is the on-line Ramsey number \widetilde{r}(H) of...
-
Evolutionary Sets of Safe Ship Trajectories: problem dedicated operators
PublicationThe paper presents the optimization process of the evolutionary sets of safe ship trajectories method, with a focus on its problem-dedicated operators. The method utilizes a customized evolutionary algorithm to solve a constrained optimization problem. This problem is defined as finding a set of cooperating trajectories (a set is an evolutionary individual) of all the ships involved in the encounter situation. The resulting trajectories...
-
Modelling and analysis of beam/bar structure by application of bond graphs
PublicationThe paper presents an uniform, port-based approach to modelling of beam/bar systems (trusses). Port-based model of such distributed parameter system has been defined by application of the bond graph methodology and the distributed transfer function method (DTFM). The proposed method of modelling enables to formulate input data for computer analysis by application of the DTFM. The constructed computational package enables the frequency...
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublicationAn edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...
-
An upper bound on the 2-outer-independent domination number of a tree
PublicationA 2-outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)D has a at least two neighbors in D, and the set V(G)D is independent. The 2-outer-independent domination number of a graph G, denoted by gamma_2^{oi}(G), is the minimum cardinality of a 2-outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_2^{oi}(T) <= (n+l)/2,...
-
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...
-
Weighted Clustering for Bees Detection on Video Images
PublicationThis work describes a bee detection system to monitor bee colony conditions. The detection process on video images has been divided into 3 stages: determining the regions of interest (ROI) for a given frame, scanning the frame in ROI areas using the DNN-CNN classifier, in order to obtain a confidence of bee occurrence in each window in any position and any scale, and form one detection window from a cloud of windows provided by...
-
Certified domination
PublicationImagine that we are given a set D of officials and a set W of civils. For each civil x ∈ W, there must be an official v ∈ D that can serve x, and whenever any such v is serving x, there must also be another civil w ∈ W that observes v, that is, w may act as a kind of witness, to avoid any abuse from v. What is the minimum number of officials to guarantee such a service, assuming a given social network? In this paper, we introduce...
-
POLAND’S ENERGY DEPENDENCE AT THE TURN OF THE 21ST CENTURY
PublicationThe following article is an attempt to assess Poland's energy independence in the years 1993-2020. The main aim of the paper is to present Poland's dependence on raw materials from foreign partners - in the field of imports of electricity, natural gas, crude oil, non-renewable energy resources, i.e., hard coal and lignite, and the country's dynamics in the amount of imports. In addition, the aim of the work is to answer research...
-
An upper bound on the total outer-independent domination number of a tree
PublicationA total outer-independent dominating set of a graph G=(V(G),E(G)) is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V(G)D is independent. The total outer-independent domination number of a graph G, denoted by gamma_t^{oi}(G), is the minimum cardinality of a total outer-independent dominating set of G. We prove that for every tree T of order n >= 4, with l leaves and s support vertices we have...
-
Turán numbers for odd wheels
PublicationThe Turán number ex(n,G) is the maximum number of edges in any n-vertex graph that does not contain a subgraph isomorphic to G. A wheel W_n is a graph on n vertices obtained from a C_{n−1} by adding one vertex w and making w adjacent to all vertices of the C_{n−1}. We obtain two exact values for small wheels: ex(n,W_5)=\lfloor n^2/4+n/2\rfloor, ex(n,W_7)=\lfloor n^2/4+n/2+1 \rfloor. Given that ex(n,W_6) is already known, this...
-
Reduced-cost electromagnetic-driven optimisation of antenna structures by means of trust-region gradient-search with sparse Jacobian updates
PublicationNumerical optimisation plays more and more important role in the antenna design. Because of lack of design-ready theoretical models, electromagnetic (EM)-simulation-driven adjustment of geometry parameters is a necessary step of the design process. At the same time, traditional parameter sweeping cannot handle complex topologies and large number of design variables. On the other hand, high computational cost of the conventional...
-
Fast EM-driven optimization using variable-fidelity EM models and adjoint sensitivities
PublicationA robust and computationally efficient technique for microwave design optimization is presented. Our approach exploits variable-fidelity electromagnetic (EM) simulation models and adjoint sensitivities. The low-fidelity EM model correction is realized by means of space mapping (SM). In the optimization process, the SM parameters are optimized together with the design itself, which allows us to keep the number...
-
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...
-
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...
-
Planning optimised multi-tasking operations under the capability for parallel machining
PublicationThe advent of advanced multi-tasking machines (MTMs) in the metalworking industry has provided the opportunity for more efficient parallel machining as compared to traditional sequential processing. It entailed the need for developing appropriate reasoning schemes for efficient process planning to take advantage of machining capabilities inherent in these machines. This paper addresses an adequate methodical approach for a non-linear...
-
Artificial Neural Network based fatigue life assessment of riveted joints in AA2024 aluminum alloy plates and optimization of riveted joints parameters
PublicationThe objective of this paper is to provide the fatigue life of riveted joints in AA2024 aluminum alloy plates and optimization of riveted joints parameters. At first, the fatigue life of the riveted joints in AA2024 aluminum alloy plates is obtained by experimental tests. Then, an artificial neural network is applied to estimate the fatigue life of riveted lap joints based on the number of lateral and longitudinal holes, punch pressure,...
-
On Symmetry of Uniform and Preferential Attachment Graphs
PublicationMotivated by the problem of graph structure compression under realistic source models, we study the symmetry behavior of preferential and uniform attachment graphs. These are two dynamic models of network growth in which new nodes attach to a constant number m of existing ones according to some attachment scheme. We prove symmetry results for m=1 and 2 , and we conjecture that for m≥3 , both models yield asymmetry with high...
-
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...
-
Degradable poly(ester-ether) urethanes of improved surface calcium deposition developed as novel biomaterials
PublicationBones, which are considered as hard tissues, work as scaffold for human body. They provide physical support for muscles and protect intestinal organs. Percentage of hard tissues in human body depends on age, weight, and gender. Human skeleton consists of 206 connected bones. Therefore, it is natural that the hard-tissue damage such as fractures, osteoporosis, and congenital lack of bone may appear. The innovative way of bone healing...
-
Complexity Issues on of Secondary Domination Number
PublicationIn this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)-domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding...
-
Generating optimal paths in dynamic environments using RiverFormation Dynamics algorithm
PublicationThe paper presents a comparison of four optimisation algorithms implemented for the purpose of finding the shortest path in static and dynamic environments with obstacles. Two classical graph algorithms –the Dijkstra complete algorithm and A* heuristic algorithm – were compared with metaheuristic River Formation Dynamics swarm algorithm and its newly introduced modified version. Moreover, another swarm algorithm has been compared...
-
Improving methods for detecting people in video recordings using shifting time-windows
PublicationWe propose a novel method for improving algorithms which detect the presence of people in video sequences. Our focus is on algorithms for applications which require reporting and analyzing all scenes with detected people in long recordings. Therefore one of the target qualities of the classification result is its stability, understood as a low number of invalid scene boundaries. Many existing methods process images in the recording...
-
A bisection‐based heuristic for rapid EM‐driven multiobjective design of compact impedance transformers
PublicationDesign of microwave structures is a multiobjective task where several conflicting requirements have to be considered at the same time. For contemporary circuits characterized by complex geometries, multiobjective optimization cannot be performed using standard population‐based algorithms due to high cost of electromagnetic (EM) evaluations. In this work, we propose a deterministic approach for fast EM‐driven multiobjective design...
-
The methodology for determining of the value of cutting power for cross cutting on optimizing sawing machine
PublicationIn the article the methodology of forecasting the energy effects of the cross-cutting process using the classical method, which takes into account the specific cutting resistance, is presented. The values of cutting power for the cross-cutting process of two types of wood (softwood and hardwood) were forecasted for the optimizing sawing machine with using presented methodology. The cross-cutting process with high values of feed...
-
Local response surface approximations and variable-fidelity electromagnetic simulations for computationally efficient microwave design optimisation
PublicationIn this study, the authors propose a robust and computationally efficient algorithm for simulation-driven design optimisation of microwave structures. Our technique exploits variable-fidelity electromagnetic models of the structure under consideration. The low-fidelity model is optimised using its local response surface approximation surrogates. The high-fidelity model is refined by space mapping with polynomial interpolation of...