Wyszukiwarka
wyświetlamy 1000 najlepszych wyników Pomoc
Wyniki wyszukiwania dla: CONVEX DOMINATING SET
-
NP-completeness of convex and weakly convex domiating set decision problems.
PublikacjaLiczby dominowania wypukłego i słabo wypukłego są nowymi rodzajami liczb dominowania. W tym artykule pokazujemy, że problemy decyzyjne dominowania wypukłegi i słabo wypukłego są NP-zupełne w przypadku grafów dwudzielnych oraz split grafów. Posługując się zmodyfikowanym algorytmem Washalla możemy w czasie wielomianowym określić, czy dany podzbiór wierzchołków grafu jest spójny bądź słabo spójny.
-
Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks
PublikacjaDominating sets find application in a variety of networks. A subset of nodes D is a (1,2)-dominating set in a graph G=(V,E) if every node not in D is adjacent to a node in D and is also at most a distance of 2 to another node from D. In networks, (1,2)-dominating sets have a higher fault tolerance and provide a higher reliability of services in case of failure. However, finding such the smallest set is NP-hard. In this paper, we...
-
Equivariant degree of convex-valued applied to set-valued BVP
PublikacjaW pracy określono stopień ekwiwariantny dla odwzorowań o wartościach zwartych i wypukłych. Zastosowano go do dowodu twierdzenia o istnieniu wielunietrywialnych rozwiązań problemu brzegowego typu Dirichleta dla inkluzji różniczkowych z warunkami wzrostu typu Bernsteina-Nagumo, z dodatkowymi symetriami
-
Equivariant degree of convex-valued maps applied to set-valued BVP
Publikacja -
Convex set of quantum states with positive partial transpose analysed by hit and run algorithm
PublikacjaThe convex set of quantum states of a composite K×K system with positive partial transpose is analysed. A version of the hit and run algorithm is used to generate a sequence of random points covering this set uniformly and an estimation for the convergence speed of the algorithm is derived. For K >3 or K=3 this algorithm works faster than sampling over the entire set of states and verifying whether the partial transpose is positive....
-
The convex domination subdivision number of a graph
PublikacjaLet G = (V;E) be a simple graph. A set D\subset V is a dominating set of G if every vertex in V - D has at least one neighbor in D. The distance d_G(u, v) between two vertices u and v is the length of a shortest (u, v)-path in G. An (u, v)-path of length d_G(u; v) is called an (u, v)-geodesic. A set X\subset V is convex in G if vertices from all (a, b)-geodesics belong to X for any two vertices a, b \in X. A set X is a convex dominating...
-
Weakly convex and convex domination numbers of some products of graphs
PublikacjaIf $G=(V,E)$ is a simple connected graph and $a,b\in V$, then a shortest $(a-b)$ path is called a $(u-v)$-{\it geodesic}. A set $X\subseteq V$ is called {\it weakly convex} in $G$ if for every two vertices $a,b\in X$ exists $(a-b)$- geodesic whose all vertices belong to $X$. A set $X$ is {\it convex} in $G$ if for every $a,b\in X$ all vertices from every $(a-b)$-geodesic belong to $X$. The {\it weakly convex domination number}...
-
Weakly convex domination subdivision number of a graph
PublikacjaA set X is weakly convex in G if for any two vertices a; b \in X there exists an ab–geodesic such that all of its vertices belong to X. A set X \subset V is a weakly convex dominating set if X is weakly convex and dominating. The weakly convex domination number \gamma_wcon(G) of a graph G equals the minimum cardinality of a weakly convex dominating set in G. The weakly convex domination subdivision number sd_wcon (G) is the minimum...
-
On proper (1,2)‐dominating sets in graphs
PublikacjaIn 2008, Hedetniemi et al. introduced the concept of (1,)-domination and obtained some interesting results for (1,2) -domination. Obviously every (1,1) -dominating set of a graph (known as 2-dominating set) is (1,2) -dominating; to distinguish these concepts, we define a proper (1,2) -dominating set of a graph as follows: a subset is a proper (1,2) -dominating set of a graph if is (1,2) -dominating and it is not a (1,1) -dominating...
-
Two Approaches to Constructing Certified Dominating Sets in Social Networks
PublikacjaSocial networks are an important part of our community. In this context, certified dominating sets help to find in networks a group of people, referring as officials, such that 1) for each civilian, there is an official that can serve the civilian, and 2) no official is adjacent to exactly one civilian, to prevent potential abuses. To delve deeper into this topic, this study considers two approaches to the problem of finding certified...
-
Modele i algorytmy dla grafowych struktur defensywnych
PublikacjaW niniejszej pracy przeprowadzono analizę złożoności istnienia struktur defensywnych oraz równowag strategicznych w grafach. W przypadku struktur defensywnych badano modele koalicji defensywnych, zbiorów defensywnych i koalicji krawędziowych – każdy z nich w wersji globalnej, tj. z wymogiem dominacji całego grafu. W przypadku modeli równowagi strategicznej badano równowagę strategiczną koalicji defensywnych, równowagę strategiczną...
-
Minimal 2-dominating sets in Trees
PublikacjaWe provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3247^n). This leads to that every tree has at most 1.3247^n minimal 2-dominating sets. We also show that thisbound is tight.
-
Minimal double dominating sets in trees
PublikacjaWe provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.
-
Trees having many minimal dominating sets
PublikacjaWe provide an algorithm for listing all minimal dominating sets of a tree of order n in time O(1.4656^n). This leads to that every tree has at most 1.4656^n minimal dominating sets. We also give an infinite family of trees of odd and even order for which the number of minimal dominating sets exceeds 1.4167^n, thus exceeding 2^{n/2}. This establishes a lower bound on the running time of an algorithm for listing all minimal dominating...
-
Reconfiguring Minimum Dominating Sets in Trees
PublikacjaWe provide tight bounds on the diameter of γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. In particular, we prove that for any tree T of order n ≥ 3, the diameter of its γ-graph is at most n/2 in the single vertex replacement adjacency model, whereas in the slide adjacency model, it is at most 2(n − 1)/3. Our proof is constructive, leading to a simple linear-time algorithm for determining...
-
On the connected and weakly convex domination numbers
PublikacjaIn this paper we study relations between connected and weakly convex domination numbers. We show that in general the difference between these numbers can be arbitrarily large and we focus on the graphs for which a weakly convex domination number equals a connected domination number. We also study the influence of the edge removing on the weakly convex domination number, in particular we show that a weakly convex domination number...
-
Influence of edge subdivision on the convex domination number
PublikacjaWe 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.
-
An Algorithm for Listing All Minimal 2-Dominating Sets of a Tree
PublikacjaWe provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3248n) . This implies that every tree has at most 1.3248 n minimal 2-dominating sets. We also show that this bound is tigh.
-
An algorithm for listing all minimal double dominating sets of a tree
PublikacjaWe provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.
-
Weakly convex and convex domination numbers.
PublikacjaW artykule przedstawione są nowo zdefiniowane liczby dominowania wypukłego i słabo wypukłego oraz ich porównanie z innymi liczbami dominowania. W szczególności, rozważana jest równość liczby dominowania spójnego i wypukłego dla grafów kubicznych.
-
A note on the weakly convex and convex domination numbers of a torus
PublikacjaW pracy określone są liczby liczby dominowania i dominowania wypukłego torusów, czyli iloczynów kartezjańskich dwóch cykli.
-
Super Dominating Sets in Graphs
PublikacjaIn this paper some results on the super domination number are obtained. We prove that if T is a tree with at least three vertices, then n2≤γsp(T)≤n−s, where s is the number of support vertices in T and we characterize the extremal trees.
-
Open-Set Speaker Identification Using Closed-Set Pretrained Embeddings
PublikacjaThe paper proposes an approach for extending deep neural networks-based solutions to closed-set speaker identification toward the open-set problem. The idea is built on the characteristics of deep neural networks trained for the classification tasks, where there is a layer consisting of a set of deep features extracted from the analyzed inputs. By extracting this vector and performing anomaly detection against the set of known...
-
Resonance microstrip structure with patch of arbitrary convex geometry with the use of field matching technique
PublikacjaAn analysis of the resonance frequency problem of planar microstrip structure with patch of arbitrary convex geometry is presented. A full-wave analysis is employed utilizing a combination of Galerkin’s moment method and field matching technique. In this approach, a field matching technique is adopted to calculate the patch surface current densities, and next the method of moments is utilized to calculate resonance frequencies...
-
Convex universal fixers
PublikacjaPraca dotyczy dominowania wypukłego w grafach pryzmowych.
-
Squashed entanglement for multipartite states and entanglement measures based on the mixed convex roof
PublikacjaNew measures of multipartite entanglement are constructedbased on two definitions of multipartite information anddifferent methods of optimizing over extensions of the states. Oneis a generalization of the squashed entanglement where one takesthe mutual information of parties conditioned on the state's extensionand takes the infimum over such extensions. Additivity ofthe multipartite squashed entanglement is proved for both versionsof...
-
Application of Doubly Connected Dominating Sets to Safe Rectangular Smart Grids
PublikacjaSmart grids, together with the Internet of Things, are considered to be the future of the electric energy world. This is possible through a two-way communication between nodes of the grids and computer processing. It is necessary that the communication is easy and safe, and the distance between a point of demand and supply is short, to reduce the electricity loss. All these requirements should be met at the lowest possible cost....
-
An absorbing set for the Chialvo map
PublikacjaThe classical Chialvo model, introduced in 1995, is one of the most important models that describe single neuron dynamics. In order to conduct effective numerical analysis of this model, it is necessary to obtain a rigorous estimate for the maximal bounded invariant set. We discuss this problem, and we correct and improve the results obtained by Courbage and Nekorkin (2010). In particular, we provide an explicit formula for an...
-
JOURNAL OF CONVEX ANALYSIS
Czasopisma -
An Analysis of Scattering from Ferrite Post of Arbitrary Convex Cross Section with the Use of Field Matching Method
PublikacjaA problem of electromagnetic wave scattering from ferrite post is presented. The post is assumed to be located in closed areas as waveguide junction, or in open area illuminated by a plane wave. The object is of arbitrary convex cross section and the method of analysis is semi-analytical, based on the direct field matching technique.
-
Corrosion degradation monitoring of ship stiffened plates using guided wave phase velocity and constrained convex optimization method
PublikacjaThe study presents an experimental investigation on the corrosion degradation level assessment using nondestructive wave-based methods. The degradation level of ship structural elements has been assessed in two different ways. The first one is based on the spectral decomposition and zero-crossing incorporated reconstruction of the dispersion curve approach of the antisymmetric Lamb wave mode and the best matching of the theoretical...
-
An Analysis of Periodic Arrangements of Cylindrical Objects of Arbitrary Convex Cross Sections with the Use of Field Matching Method
PublikacjaA problem of electromagnetic wave scattering from multilayered frequency selective surfaces is presented. Each surface is composed of periodically arranged cylindrical posts of arbitrary convex cross-section. The method of analysis is based on the direct field matching technique for a single cell, and the transmission matrix method with the lattice sums technique for periodic arrangement of scatterers.
-
Photovoltaic demonstration set up
PublikacjaThe use of photovoltaics is growing rapidly in the industry as well as households. Therefore, educating the public will help them understand solar cell technology, which is becoming more common in everyday life. This paper proposes a demonstrational set-up of photovoltaic panel for the purpose of science education. It was used in numerous outreach activities such as science fairs. Moreover, it proved to be a great tool for education...
-
A study of jet impingement cooling enhancement by concave and convex heat sink shape modifications
PublikacjaThe rising demand for efficient cooling technologies is a strong driver of extensive research in this area. This trend is particularly strong in turbines and microprocessors technology. Presented study is focused on the jet impingement cooling concept, which is used in various configurations for many years. The potential of the heat sink shape modification is not yet fully explored. Available literature suggests that average Nusselt...
-
Control of a vapour microturbine set in cogeneration applications
PublikacjaSystems with microturbines are implemented for local generation of heat and electricity. This paper presents the analysis of control concepts for a vapour microturbine set with a generator with permanent magnets, intended to work in small heat and power plants. Control system variants differed by the selection of controlled signals and set parameters. Possible ways of control were discussed and compared with experimentally determined...
-
SET-VALUED ANALYSIS
Czasopisma -
Developing an Ontology from Set of Experience KnowledgeStructure
PublikacjaWhen referring to knowledge forms,collecting for all decision eventsin a knowledge-explicit way becomes a significant ask for any company. Set of experience knowledge structure can assis in accomplishing this purpose.However,after collecting,distributing and sharing that knowledge as adecisional DNA is even a more important advance.Distributing and sharing companies' decisional DNA through an efficient development of Ontologies...
-
On bipartization of cubic graphs by removal of an independent set
PublikacjaWe study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set.
-
Graphs with convex domination number close to their order
PublikacjaW pracy opisane są grafy z liczbą dominowania wypukłego bliską ilości ich wierzchołków.
-
Selections and approximations of convex-valued equivariant mappings
PublikacjaUdowodniono szereg twierdzeń o współzmienniczych selekcjach i aproksymacjach ciągłych, mierzalnych i typu Caratheodory'ego dla odwzorowań G-współzmienniczych o wartościach wypukłych, gdzie G jest grupą zwartą Liego. Tw. typu Michaela, Celliny, Browdera, Kuratowskiego-Ryll-Nardzewskiego, Castaing itd.
-
Journal of Nonlinear and Convex Analysis
Czasopisma -
Asymptotic behaviour in the set of nonhomogeneous chains of stochastic operators
PublikacjaWe study different types of asymptotic behaviour in the set of (infinite dimensional) nonhomogeneous chains of stochastic operators acting on L1(μ) spaces. In order to examine its structure we consider different norm and strong operator topologies. To describe the nature of the set of nonhomogeneous chains of Markov operators with a particular limit behaviour we use the category theorem of Baire. We show that the geometric structure...
-
Music Genre Recognition in the Rough Set-Based Environment
PublikacjaThe aim of this paper is to investigate music genre recognition in the rough set-based environment. Experiments involve a parameterized music data-base containing 1100 music excerpts. The database is divided into 11 classes cor-responding to music genres. Tests are conducted using the Rough Set Exploration System (RSES), a toolset for analyzing data with the use of methods based on the rough set theory. Classification effectiveness...
-
GreedyMAX-type Algorithms for the Maximum Independent Set Problem
PublikacjaA maximum independent set problem for a simple graph G = (V,E) is to find the largest subset of pairwise nonadjacent vertices. The problem is known to be NP-hard and it is also hard to approximate. Within this article we introduce a non-negative integer valued functionp defined on the vertex set V(G) and called a potential function of agraph G, while P(G) = max{vinV(G)| p(v)} is called a potential of G. For any graph P(G) <= D(G),...
-
Nordhaus-Gaddum results for the convex domination number of a graph
PublikacjaPraca dotyczy nierówności typu Nordhausa-Gadduma dla dominowania wypukłego.
-
OVERALL SET OF BANDSAW TEETH VERSUS METHODS OF MEASUREMENTS
PublikacjaThis article deals with the impact of the manual methods of measurement on the overall set measurement results. It describes the results of the measurement of bandsaw teeth kerf with the use of a micrometer and a digital calliper. It is commonly known that the cutting process causes the wear of cutting tools. The wear of the cutting edge depends on the cutting conditions as well as on the mechanical properties of the processed...
-
Prevalence Problem in the Set of Quadratic Stochastic Operators Acting on L1
PublikacjaThis paper is devoted to the study of the problem of prevalence in the class of quadratic stochastic operators acting on the L1 space for the uniform topology. We obtain that the set of norm quasi-mixing quadratic stochastic operators is a dense and open set in the topology induced by a very natural metric. This shows the typical long-term behaviour of iterates of quadratic stochastic operators.
-
Numerical Analysis of TB32 Crash Tests for 4-cable Guardrail Barrier System Installed on the Horizontal Convex Curves of Road
PublikacjaHorizontal curves are one of the elements of road infrastructure where statistically a relatively high number of accidents have been reported. In the last ten years in Poland approx. 10% of all road accidents happened on horizontal curves of roads and was responsible for approx. 14% of all fatalities on Polish roads. Thus, this issue is important and requires extensive research and proper road safety treatments. One possible measure...
-
ALLYING SYSTEM THINKING AND SET OF EXPERIENCE KNOWLEDGE STRUCTURE
PublikacjaThe approach of system thinking is completely different from traditional forms of analysis. Even the ancient meaning of word analysis is “a breaking up”. Set of Experience Knowledge Structure is an atomic record of decision event that can be grouped together and form some form of decision DNA of an organization. The question that this paper is trying to answer in how those concepts can be merged.
-
The Usage of the BP-Layers Stereo Matching Algorithm with the EBCA Camera Set
PublikacjaThis paper is concerned with applying a stereo matching algorithm called BP-Layers to a set of many cameras. BP Layers is designed for obtaining disparity maps from stereo cameras. The algorithm takes advantage of convolutional natural networks. This paper presents using this algorithm with a set called Equal Baseline Camera Array. This set consists of up to five cameras with one central camera and other ones aground it. Such a...