Search
Search results for: interval graph coloring
-
Decontaminating Arbitrary Graphs by Mobile Agents: a Survey
PublicationA team of mobile agents starting from homebases need to visit and clean all nodes of the network. The goal is to find a strategy, which would be optimal in the sense of the number of needed entities, the number of moves performed by them or the completion time of the strategy. Currently, the field of distributed graph searching by a team of mobile agents is rapidly expanding and many new approaches and models are being presented...
-
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...
-
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...
-
Embedded Representations of Wikipedia Categories
PublicationIn this paper, we present an approach to building neural representations of the Wikipedia category graph. We test four different methods and examine the neural embeddings in terms of preservation of graphs edges, neighborhood coverage in representation space, and their influence on the results of a task predicting parent of two categories. The main contribution of this paper is application of neural representations for improving the...
-
Hat problem on odd cycles
PublicationThe topic is the hat problem in which each of n players is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of a win. In this version every player can...
-
The values of Permutation Entropy for individuals with Normal Sinus Rhythm
Open Research DataThe dataset consists of calculated values of entropy of 75 000 intervals between consecutive heartbeats (RR intervals) for 54 patients with normal sinus rhythm (NSR). The original data were taken from PhysioNet Normal Sinus Rhythm RR Interval Database (cf. Goldberger A., Amaral L., Glass L., Hausdorff J., Ivanov P.C., Mark R., Mietus J.E., Moody G.B.,...
-
The values of Permutation Entropy for patients with Congestive Heart Failure
Open Research DataThe dataset consists of calculated values of entropy of 75 000 intervals between consecutive heartbeats (RR intervals) for 29 patients with congestive heart failure (CHF). The original data were taken from PhysioNet Congestive Heart Failure RR Interval Database (cf. Goldberger A., Amaral L., Glass L., Hausdorff J., Ivanov P.C., Mark R., Mietus J.E.,...
-
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...
-
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...
-
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,...
-
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 2-bondage number of G, denoted by b_2(G), is the minimum cardinality among all sets of edges E' subseteq E such that gamma_2(G-E') > gamma_2(G). If for every E' subseteq E we have...
-
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|...
-
Robust output prediction of differential – algebraic systems – application to drinking water distribution system
PublicationThe paper presents the recursive robust output variable prediction algorithm, applicable for systems described in the form of nonlinear algebraic-differential equations. The algorithm bases on the uncertainty interval description, the system model, and the measurements. To improve the algorithm efficiency, nonlinear system models are linearised along the nominal trajectory. The effectiveness of the algorithm is demonstrated on...
-
The values of Block Entropy for individuals with Normal Sinus Rhythm
Open Research DataThe dataset consists of calculated values of entropy of 75 000 intervals between consecutive heartbeats (RR intervals) for 54 patients with normal sinus rhythm (NSR). The original data were taken from PhysioNet Normal Sinus Rhythm RR Interval Database (cf. Goldberger A., Amaral L., Glass L., Hausdorff J., Ivanov P.C., Mark R., Mietus J.E., Moody G.B.,...
-
The values of Block Entropy for patients with Congestive Heart Failure
Open Research DataThe dataset consists of calculated values of entropy of 75 000 intervals between consecutive heartbeats (RR intervals) for 29 patients with congestive heart failure (CHF). The original data were taken from PhysioNet Congestive Heart Failure RR Interval Database (cf. Goldberger A., Amaral L., Glass L., Hausdorff J., Ivanov P.C., Mark R., Mietus J.E.,...
-
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...
-
On trees attaining an upper bound on the total domination number
PublicationA total 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. The total domination number of a graph G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. Chellali and Haynes [Total and paired-domination numbers of a tree, AKCE International Journal of Graphs and Combinatorics 1 (2004), 69-75] established the following upper bound on the total domination...
-
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,...
-
On trees with double domination number equal to 2-domination number plus one
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A subset D subseteq V(G) is a 2-dominating set of G if every vertex of V(G)D is dominated by at least two vertices of D, while it is a double dominating set of G if every vertex of G is dominated by at least two vertices of D. The 2-domination (double domination, respectively) number of a graph G is the minimum cardinality of a 2-dominating (double dominating,...
-
Finding small-width connected path decompositions in polynomial time
PublicationA connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers...
-
Software tool for modelling of mechatronic systems with elastic continua
PublicationThe paper presents a systematic computational package for modelling and analysis of complex systems composed of multiple lumped and distributed parameter subsystems. The constructed computer program enables the frequency domain analysis of a class of linear systems and to obtain reduced order model in the form of bond graph. Obtained modal bond graph can be directly exported into 20-Sim package to further processing including nonlinear...
-
Weighted 2-sections and hypergraph reconstruction
PublicationIn the paper we introduce the notion of weighted 2-sections of hypergraphs with integer weights and study the following hypergraph reconstruction problems: (1) Given a weighted graph , is there a hypergraph H such that is its weighted 2-section? (2) Given a weighted 2-section , find a hypergraph H such that is its weighted 2-section. We show that (1) is NP-hard even if G is a complete graph or integer weights w does not exceed...
-
Methods of measurement signal acquisition from the rotational flow meter for frequency analysis
PublicationOne of the simplest and commonly used instruments for measuring the flow of homogeneous substances is the rotational flow meter. The main part of such a device is a rotor (vane or screw) rotating at a speed which is the function of the fluid or gas flow rate. A pulse signal with a frequency proportional to the speed of the rotor is obtained at the sensor output. For measurements in dynamic conditions, a variable interval between...
-
A Note on Shannon Capacity for Invariant and Evolving Channels
PublicationIn the paper we discuss the notion of Shannon capacity for invariant and evolving channels. We show how this notion is involved in information theory, graph theory and Ramsey theory.
-
An Efficient Noisy Binary Search in Graphs via Median Approximation
PublicationConsider a generalization of the classical binary search problem in linearly sorted data to the graph-theoretic setting. The goal is to design an adaptive query algorithm, called a strategy, that identifies an initially unknown target vertex in a graph by asking queries. Each query is conducted as follows: the strategy selects a vertex q and receives a reply v: if q is the target, then =, and if q is not the target, then v is a...
-
Eigenfaces, Fisherfaces, Laplacianfaces, Marginfaces – How to Face the Face Verification Task
PublicationThis paper describes the exhaustive tests of four known methods of linear transformations (Eigenfaces, Fisherfaces, Laplacianfaces and Marginfaces) in the context of face verification task. Additionally, we introduce a new variant of the transformation (Laplacianface + LDA), and the specific interval-based decision rule. Both of them improve the performance of face verification, in general, however, our experiments show that the...
-
Paired domination versus domination and packing number in graphs
PublicationGiven a graph G = (V(G), E(G)), the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph G are denoted by γ (G), γpr(G), and γt(G), respectively. For a positive integer k, a k-packing in G is a set S ⊆ V(G) such that for every pair of distinct vertices u and v in S, the distance between u and v is at least k + 1. The k-packing number is the order of a largest kpacking and...
-
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...
-
Quantum strategies for rendezvous and domination tasks on graphs with mobile agents
PublicationThis paper explores the application of quantum nonlocality, a renowned and unique phenomenon acknowledged as a valuable resource. Focusing on an alternative application, we demonstrate its quantum advantage for mobile agents engaged in specific distributed tasks without communication. The research addresses the significant challenge of rendezvous on graphs and introduces a distributed task for mobile agents grounded in the graph...
-
Drawing maps with advice
PublicationW pracy podejmujemy temat konstrukcji algorytmu dla agenta, który zostaje umieszczony w dowolnym wierzchołku grafu (wierzchołki są nierozróżnialne, krawędzie mają etykiety portów), po czym realizuje algorytm zmierzający do znalezienia drzewa spinającego grafu lub izomorficznej kopii grafu. Dla obu problemów podajemy asymptotycznie dokładne lub prawie dokładne oszacowania na ilość bitów dodatkowej informacji, którą agent musi otrzymać...
-
Conley-Morse graphs for a two-patch vaccination model
Open Research DataThis dataset contains selected results of rigorous numerical computations described in Section 5 of the paper "Rich bifurcation structure in a two-patch vaccination model" by D.H. Knipl, P. Pilarczyk, G. Röst, published in SIAM Journal on Applied Dynamical Systems (SIADS), Vol. 14, No. 2 (2015), pp. 980–1017, doi: 10.1137/140993934.
-
A bound on the number of middle-stage crossbars in f-cast rearrangeable Clos networks
PublicationIn 2006 Chen and Hwang gave a necessary and sufficient condition under which a three-stage Clos network is rearrangeable for broadcast connections. Assuming that only crossbars of the first stage have no fan-out property, we give similar conditions for f-cast Clos networks, where f is an arbitrary but fixed invariant of the network. Such assumptions are valid for some practical switching systems, e.g. high-speed crossconnects....
-
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)....
-
Non-isolating bondage in graphs
PublicationA dominating set of a graph $G = (V,E)$ is a set $D$ of vertices of $G$ such that every vertex of $V(G) \setminus D$ has a neighbor in $D$. The domination number of a graph $G$, denoted by $\gamma(G)$, is the minimum cardinality of a dominating set of $G$. The non-isolating bondage number of $G$, denoted by $b'(G)$, is the minimum cardinality among all sets of edges $E' \subseteq E$ such that $\delta(G-E') \ge 1$ and $\gamma(G-E')...
-
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...
-
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...
-
New Approach to Noncasual Identification of Nonstationary Stochastic FIR Systems Subject to Both Smooth and Abrupt Parameter Changes
PublicationIn this technical note, we consider the problem of finite-interval parameter smoothing for a class of nonstationary linear stochastic systems subject to both smooth and abrupt parameter changes. The proposed parallel estimation scheme combines the estimates yielded by several exponentially weighted basis function algorithms. The resulting smoother automatically adjusts its smoothing bandwidth to the type and rate of nonstationarity...
-
Sport-related concussion alters cerebral hemodynamic activity during controlled respiration
PublicationThis study investigated cerebral hemodynamic activity following sport-related concussion. Prefrontal cortex oxygenation was assessed by near-infrared spectroscopy (NIRS) during a controlled breathing protocol. Wavelet transformation of the NIRS signals showed significant decreases in HbO2 and HbD amplitude at the respiratory frequency interval (0.10–0.6 HZ) from preseason baseline to acute concussion. These results suggest a decreased...
-
Fractional Problems with Right-Handed Riemann-Liouville Fractional Derivatives
PublicationIn this paper, we investigate the existence of solutions for advanced fractional differential equations containing the right-handed Riemann-Liouville fractional derivative both with nonlinear boundary conditions and also with initial conditions given at the end point T of interval [0,T ]. We use both the method of successive approximations, the Banach fixed point theorem and the monotone iterative technique, as well. Linear problems...
-
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...
-
IZOLACJA I IDENTYFIKACJA NATURALNYCH SUBSTANCJI BARWIĄCYCH OBECNYCH W PRÓBKACH FARB ARTYSTYCZNYCH I TKANINACH POCHODZENIA HISTORYCZNEGO
PublicationNatural organic dyes are group of substances that belong to various types of chemical compounds. The most commonly used in paintings and dyeing textiles were naturally occurring dyestuffs from group of anthraquinones, flavones and indigoid dyes. Identification of coloring substances present in historical artistic paints provides relevant information for a wide range of specialists dealing with works of art and in the field of conservation science....
-
A risk comparison framework for autonomous ships navigation
PublicationMaritime autonomous surface ships (MASS) may operate in three predefined operational modes (OM): manual, remote, or autonomous control. Determining the appropriate OM for MASS is important for operators and competent authorities that monitor and regulate maritime traffic in given areas. However, a science-based approach to this respect is currently unavailable. To assist the selection of the proper OM, this study presents a risk-based...
-
Fractional problems with advanced arguments
PublicationThis paper concerns boundary fractional differential problems with advanced arguments. We investigate the existence of initial value problems when the initial point is given at the end point of an interval. Nonhomogeneous linear fractional differential equations are also studied. The existence of solutions for fractional differential equations with advanced arguments and with boundary value problems has been investigated by using...
-
Modeling and analysis of the effectiveness of the guard systemswith dynamic graphs
PublicationIn the following paper it will be presented a new model for analysis (in polynomial time) of the effectiveness of the guard systems. Therewill be presented its practical applications in problems such as searching for the weakest points of the system, planning guards' paths or cameras deployment, switching image from multiple cameras on several monitors, or interception of the intruder. This model is based on describing the guarded...
-
Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs
PublicationGiven a graph G= (V, E), the subdivision of an edge e=uv∈E(G) means the substitution of the edge e by a vertex x and the new edges ux and xv. The domination subdivision number of a graph G is the minimum number of edges of G which must be subdivided (where each edge can be subdivided at most once) in order to increase the domination number. Also, the domination multisubdivision number of G is the minimum number of subdivisions...
-
The complexity of bicriteria tree-depth
PublicationThe tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph G. We introduce a bicriteria generalization in which additionally the width of the elimination tree needs to be bounded by some input integer b. We are interested in the case when G is the line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive 2b-approximation algorithm. This particular...
-
Capacity analysis of the selected track system in partially ordered space
PublicationA proper location of the interval sections has significant impact on the traffic flow in the railway track network. This issue is critical during line modernization as well as when a new solution accounting for the traffic forecast at particular element of the railway track network is developed . However, the situation is more complex and more expensive for railway stations since improvement of the capacity requires critical organizational...
-
Generalized Savitzky–Golay filters for identification of nonstationary systems
PublicationThe problem of identification of nonstationary systems using noncausal estimation schemes is consid-ered and a new class of identification algorithms, combining the basis functions approach with localestimationtechnique,isdescribed.Unliketheclassicalbasisfunctionestimationschemes,theproposedlocal basis function estimators are not used to obtain interval approximations of the parametertrajectory, but provide a sequence of point...
-
Errors of a Linear Current Approximation in High-Speed PMSM Drives
PublicationCurrent sampling techniques and predictive algorithms used in the digital control of electric drives rely on a simple mathematical model that assumes linear current changes upon constant supplying voltages. This paper identifies rotor movement as a factor that makes this assumption invalid when the rotor covers an angular distance of a few tens of degrees during the control interval duration. The errors of the linear current approximation...
-
The Effect of Full-Cell Impregnation of Pine Wood (Pinus sylvestris L.) on Changes in Electrical Resistance and on the Accuracy of Moisture Content Measurement Using Resistance Meters
PublicationThe impact of the full-cell impregnation of pine wood was investigated with respect to changes in electrical resistance and the accuracy of moisture content measurement. This study compared the resistance of impregnated and untreated pine timber harvested from the northern part of Poland (Pomeranian region). The wood was impregnated by the vacuum-pressure method. The preservative (TANALITH E 3475) and coloring (TANATONE 3950) agents...