Search
displaying 1000 best results Help
Search results for: MINIMAL DOMINATING SET
-
Trees having many minimal dominating sets
PublicationWe 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...
-
Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks
PublicationDominating 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...
-
Minimal 2-dominating sets in Trees
PublicationWe 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
PublicationWe 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.
-
An Algorithm for Listing All Minimal 2-Dominating Sets of a Tree
PublicationWe 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
PublicationWe 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.
-
Graphs with equal domination and certified domination numbers
PublicationA setDof vertices of a graphG= (VG,EG) is a dominating set ofGif every vertexinVG−Dis adjacent to at least one vertex inD. The domination number (upper dominationnumber, respectively) ofG, denoted byγ(G) (Γ(G), respectively), is the cardinality ofa smallest (largest minimal, respectively) dominating set ofG. A subsetD⊆VGis calleda certified dominating set ofGifDis a dominating set ofGand every vertex inDhas eitherzero...
-
Total Domination Versus Domination in Cubic Graphs
PublicationA dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...
-
On proper (1,2)‐dominating sets in graphs
PublicationIn 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...
-
Redukcja czasu analizy MZP przez ograniczenie rozmiaru rozwiązania
PublicationAnaliza drzew niezdatności jest uznaną metodą analizy bezpieczeństwa systemów. Notacja ECSDM pozwala definiować zależności czasowe między zdarzeniami drzewa oraz przeanalizować je w celu określenia zależności pomiędzy zdarzeniami z Minimalnych Zbiorów Przyczyn (MZP). Dzięki wprowadzeniu klasyfikacji zdarzeń z MZP można wyodrębnić zależności czasowe istotne dla zapobiegania wywoływania hazardu przez konkretny MZP. Pozostałe zależności...
-
Reconfiguring Minimum Dominating Sets in Trees
PublicationWe 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...
-
Periodic expansion in determining minimal sets of Lefschetz periods for Morse–Smale diffeomorphisms
PublicationWe apply the representation of Lefschetz numbers of iterates in the form of periodic expansion to determine the minimal sets of Lefschetz periods of Morse–Smale diffeomorphisms. Applying this approach we present an algorithmic method of finding the family of minimal sets of Lefschetz periods for Ng, a non-orientable compact surfaces without boundary of genus g. We also partially confirm the conjecture of Llibre and Sirvent (J Diff...
-
Vehicle detector training with minimal supervision
PublicationRecently many efficient object detectors based on convolutional neural networks (CNN) have been developed and they achieved impressive performance on many computer vision tasks. However, in order to achieve practical results, CNNs require really large annotated datasets for training. While many such databases are available, many of them can only be used for research purposes. Also some problems exist where such datasets are not...
-
Minimal surfaces and conservation laws for bidimensional structures
PublicationWe discuss conservation laws for thin structures which could be modeled as a material minimal surface, i.e., a surface with zero mean curvatures. The models of an elastic membrane and micropolar (six-parameter) shell undergoing finite deformations are considered. We show that for a minimal surface, it is possible to formulate a conservation law similar to three-dimensional non-linear elasticity. It brings us a path-independent...
-
Incremental construction of Minimal Tree Automata [online]
PublicationWe describe an algorithm that allows the incremental addition or removal of unranked ordered trees to minimal frontier-to-root deterministic tree automaton (DTA). The algorithm takes a tree t and a minimal DTA A as input; it outputs a minimal DTA A' which accepts the language L(A) accepted by A incremented (or decremented) with the tree t. The algorithm can be used to efficiently maintain dictionaries which store large collections...
-
Super Dominating Sets in Graphs
PublicationIn 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
PublicationThe 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...
-
Perfect hashing with pseudo-minimal bottom-up deterministic tree automata
PublicationWe describe a technique that maps unranked trees to their hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to techniques implemented with minimal tree automata, our procedure builds a pseudo-minimal DTA. Pseudo-minimal automata are larger than the minimal ones but in turn the mapping can be arbitrary, so it can be determined prior to the automaton construction. We also provide procedures to build incrementally...
-
Minimal Sets of Lefschetz Periods for Morse-Smale Diffeomorphisms of a Connected Sum of g Real Projective Planes
PublicationThe dataset titled Database of the minimal sets of Lefschetz periods for Morse-Smale diffeomorphisms of a connected sum of g real projective planes contains all of the values of the topological invariant called the minimal set of Lefschetz periods, computed for Morse-Smale diffeomorphisms of a non-orientable compact surface without boundary of genus g (i.e. a connected sum of g real projective planes), where g varies from 1 to...
-
Application of Doubly Connected Dominating Sets to Safe Rectangular Smart Grids
PublicationSmart 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
PublicationThe 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...
-
Minimal number of periodic points of smooth boundary-preserving self-maps of simply-connected manifolds
PublicationLet M be a smooth compact and simply-connected manifold with simply-connected boundary ∂M, r be a fixed odd natural number. We consider f, a C1 self-map of M, preserving ∂M . Under the assumption that the dimension of M is at least 4, we define an invariant Dr(f;M,∂M) that is equal to the minimal number of r-periodic points for all maps preserving ∂M and C1-homotopic to f. As an application, we give necessary and sufficient...
-
SET-VALUED ANALYSIS
Journals -
A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata
PublicationWe describe a technique that maps unranked trees to arbitrary hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to other hashing techniques based on automata, our procedure builds a pseudo-minimal DTA for this purpose. A pseudo-minimal automaton may be larger than the minimal one accepting the same language but, in turn, it contains proper elements (states or transitions that are unique) for every input...
-
Photovoltaic demonstration set up
PublicationThe 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...
-
Journal of Minimal Access Surgery
Journals -
Randomness Amplification under Minimal Fundamental Assumptions on the Devices
PublicationRecently, the physically realistic protocol amplifying the randomness of Santha-Vazirani sources producing cryptographically secure random bits was proposed; however, for reasons of practical relevance, the crucial question remained open regarding whether this can be accomplished under the minimal conditions necessary for the task. Namely, is it possible to achieve randomness amplification using only two no-signaling components...
-
Control of a vapour microturbine set in cogeneration applications
PublicationSystems 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...
-
Database of the minimal sets of Lefschetz periods for Morse-Smale diffeomorphisms of a connected sum of g tori
Open Research DataMorse–Smale diffeomorphisms, structurally stable and having relatively simple dynamics, constitute an important subclass of diffeomorphisms that have been carefully studied during past decades. For a given Morse–Smale diffeomorphism one can consider “Minimal set of Lefschetz periods”, which provides the information about the set of periodic points of...
-
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.
-
Developing an Ontology from Set of Experience KnowledgeStructure
PublicationWhen 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...
-
Determination of the minimal critical rotational speeds of the circular saw blades with the quasi-twin resonant frequencies
PublicationTo determine the minimal critical rotational speeds of the circular saw blades is the fundamental aspect of obtaining the range of the rotational operating speeds, by which the circular saw blade can work with required stability. While for the circular saw blades with full-homogeneous bodies the determination of such rotational speeds is the relatively low level of difficulty function, whereas for circular saw blades with more...
-
Asymptotic behaviour in the set of nonhomogeneous chains of stochastic operators
PublicationWe 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
PublicationThe 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...
-
Post-comatose patients with minimal consciousness tend to preserve reading comprehension skills but neglect syntax and spelling
PublicationModern eye tracking technology provides a means for communication with patients suffering from disorders of consciousness (DoC) or remaining in locked-in-state. However, being able to use an eye tracker for controlling text-based contents by such patients requires preserved reading ability in the first place. To our knowledge, this aspect, although of great social importance, so far has seemed to be neglected. In the paper, we...
-
Set-Valued and Variational Analysis
Journals -
Database of the minimal sets of Lefschetz periods for Morse-Smale diffeomorphisms of a connected sum of g real projective planes.
Open Research DataMorse–Smale diffeomorphisms, structurally stable and having relatively simple dynamics, constitute an important subclass of diffeomorphisms that were carefully studied during past decades. For a given Morse–Smale diffeomorphism one can consider “Minimal set of Lefschetz periods”, which provides the information about the set of periodic points of considered...
-
GreedyMAX-type Algorithms for the Maximum Independent Set Problem
PublicationA 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),...
-
Prevalence Problem in the Set of Quadratic Stochastic Operators Acting on L1
PublicationThis 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.
-
OVERALL SET OF BANDSAW TEETH VERSUS METHODS OF MEASUREMENTS
PublicationThis 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...
-
Minimal and maximal solutions of differential equations with a singularmatrix.
PublicationPraca dotyczy zagadnień początkowych dla układów równań różniczkowych z macierzą osobliwą. Równania różniczkowo-algebraiczne są szczególnym przypadkiem takich zagadnień.Stosując metodę iteracji monotonicznych pokazano, że przy pewnych założeniach problem wyjściowy ma ekstremalne rozwiązania w pewnym sektorze.Teoretyczne rozważania zilustrowano przykładem.
-
Minimal transverse reinforcement of reinforced concrete members
PublicationW pierwszej części pracy omówiono zagadnienia dotyczące minimalnego zbrojenia na ścinanie elementów żelbetowych w kontekście norm europejskich oraz pozaeuropejskich. W drugiej części pracy dokonano analizy wyników badań eksperymentalnych dotyczących nośności elementów bez zbrojenia poprzecznego, które stanowią podstawę do weryfikacji zaleceń normowych w zakresie minimalnego zbrojenia na ścinanie.
-
Mixed systems with minimal and maximal lifetime variances
PublicationRozważa się mieszane układy złożone ze stałej liczby składników, których czasy zycia są niezależnymi zmiennymi losowymi o jednakowym rozkładzie i dodatniej wariancji. Bada się minimalną i maksymalną wariancję czasu życia rozważanych układów.
-
Minimal parameter implicit solvent model for ab initioelectronic-structure calculations
PublicationAbstract - We present an implicit solvent model for ab initio electronic-structure calculations which is fully self-consistent and is based on direct solution of the nonhomogeneous Poisson equation. The solute cavity is naturally defined in terms of an isosurface of the electronic density according to the formula of Fattebert and Gygi (J. Comput. Chem., 23 (2002) 662). While this model depends on only two parameters, we demonstrate...
-
ALLYING SYSTEM THINKING AND SET OF EXPERIENCE KNOWLEDGE STRUCTURE
PublicationThe 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
PublicationThis 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...
-
Stereo Camera Upgraded to Equal Baseline Multiple Camera Set (EBMCS)
PublicationThe paper presents the results of using a set of five cameras called Equal Baseline Multiple Camera Set (EBMCS) for making 3D images, disparity maps and depth maps. Cameras in the set are located in the vicinity of each other and therefore the set can be used for the purpose of stereoscopy similarly as a stereo camera.EBMCS provides disparity maps and depth maps which have a better quality than these maps obtained with the use...
-
Improving depth maps of plants by using a set of five cameras
PublicationObtaining high-quality depth maps and disparity maps with the use of a stereo camera is a challenging task for some kinds of objects. The quality of these maps can be improved by taking advantage of a larger number of cameras. The research on the usage of a set of five cameras to obtain disparity maps is presented. The set consists of a central camera and four side cameras. An algorithm for making disparity maps called multiple...
-
An algorithmic approach to estimating the minimal number of periodic points for smooth self-maps of simply-connected manifolds
PublicationFor a given self-map f of M, a closed smooth connected and simply-connected manifold of dimension m 4, we provide an algorithm for estimating the values of the topological invariant D^m_r [f], which equals the minimal number of r-periodic points in the smooth homotopy class of f. Our results are based on the combinatorial scheme for computing D^m_r [f] introduced by G. Graff and J. Jezierski [J. Fixed Point Theory Appl. 13 (2013),...
-
May dithiophosphoric acid participate in the set process?
PublicationZastosowano otrzymane S-tioacyloditiofosforany jako odczynniki tioacylujące do syntezy kwasów tiohydroksamowych. Dla większości N-alkilohydroksyloamin produktem tej reakcji były żądane kwasy tiohydroksamowe. Natomiast gdy substratem jest hydroksyloamina zawierająca duży objętościowo podstawnik na atomie azotu lub gdy posiada dwa podstawniki na atomie azotu w reakcji tej tworzą się wyłącznie odpowiednie O-tioacylohydroksyloaminy....