Wyszukiwarka
Filtry
wszystkich: 621
-
Katalog
Wyniki wyszukiwania dla: interval graph coloring
-
On-line Search in Two-Dimensional Environment
PublikacjaWe consider the following on-line pursuit-evasion problem. A team of mobile agents called searchers starts at an arbitrary node of an unknown network. Their goal is to execute a search strategy that guarantees capturing a fast and invisible intruder regardless of its movements using as few searchers as possible. We require that the strategy is connected and monotone, that is, at each point of the execution the part of the graph...
-
Certified domination
PublikacjaImagine 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...
-
A Centralized Reputation System for MANETs Based on Observed Path Performance
PublikacjaA reputation system for MANETs is described that attempts to deduce nodal trustworthiness (forwarding behaviour) from observed end-to-end path performance. The trustworthiness deduction algorithm produces interval estimates and works well if node misbehaviour is not selec-tive with respect to traversing paths. Nodal reputation levels are next calculated in the spirit of generous tit-for-tat so as to best reflect momentary nodal...
-
Optimization of the efficiency of braking energy recovery in rail transport by changing arrival time
PublikacjaThe article refers to the previous work of the authors, in which the model of traffic organization of cooperating trains including the optimization of the use of energy returned to the catenary was presented. In the presented article, the model was modified by changing the main control variable, which affects the efficient use of energy. Departure time was changed for the arrival time of the train to the stop or station. The optimization...
-
Focus on Misinformation: Improving Medical Experts’ Efficiency of Misinformation Detection
PublikacjaFighting medical disinformation in the era of the global pandemic is an increasingly important problem. As of today, automatic systems for assessing the credibility of medical information do not offer sufficient precision to be used without human supervision, and the involvement of medical expert annotators is required. Thus, our work aims to optimize the utilization of medical experts’ time. We use the dataset of sentences taken...
-
Optymalizacja efektywności hamowania odzyskowego w transporcie szynowym przez sterowanie czasem przyjazdu na stację
PublikacjaArtykuł nawiązuje do poprzednich prac autorów, w których przedstawiono model organizacji ruchu kooperujących pociągów z uwzględnieniem optymalizacji wykorzystania energii zwracanej do sieci jezdnej. W przedstawionej pracy zmodyfikowano model zmieniając główną zmienną sterującą, mającą wpływ na efektywne wykorzystanie energii, z czasu odjazdu na czas przyjazdu pociągu na stację lub przystanek. Optymalizacja dokonywana jest przez...
-
A city is not a tree: a multi-city study on street network and urban life
PublikacjaChristopher Alexander, a British-American scholar, differentiated an old (natural) city from a new (planned) one by structure. The former resembles a “semilattice”, or a complex system encompassing many interconnected sub-systems. The latter is shaped in a graph-theoretical “tree”, which lacks the structural complexity as its sub-systems are compartmentalized into a single hierarchy. This structural distinction explains why, or...
-
On trees with equal domination and total outer-independent domination numbers
PublikacjaFor a graph G=(V,E), a subset D subseteq V(G) is a dominating set if every vertex of V(G)D has a neighbor in D, while it is a total outer-independent dominating set if every vertex of G has a neighbor in D, and the set V(G)D is independent. The domination (total outer-independent domination, respectively) number of G is the minimum cardinality of a dominating (total outer-independent dominating, respectively) set of G. We characterize...
-
On trees with equal 2-domination and 2-outer-independent domination numbers
PublikacjaFor a graph G = (V,E), a subset D \subseteq V(G) is a 2-dominating set if every vertex of V(G)\D$ has at least two neighbors in D, while it is a 2-outer-independent dominating set if additionally the set V(G)\D is independent. The 2-domination (2-outer-independent domination, respectively) number of G, is the minimum cardinality of a 2-dominating (2-outer-independent dominating, respectively) set of G. We characterize all trees...
-
The Snow Team Problem
PublikacjaWe study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset~$\cS$ of vertices of a digraph $D$ and a positive integer $k$, the objective is to determine whether there is a subgraph $H=(\cV_H,\cA_H)$ of $D$ such that (a) $\cS \subseteq \cV_H$, (b)...
-
Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
PublikacjaThe problem of scheduling n identical jobs on 4 uniform machines with speeds s1>=s2>=s3>=s4 is considered.The aim is to find a schedule with minimum possible length. We assume that jobs are subject to mutual exclusion constraints modeled by a bipartite incompatibility graph of degree delta. We show that the general problem is NP-hard even if s1=s2=s3. If, however, delta<5 and s1>12s2 s2=s3=s4, then the problem can be solved to...
-
Asynchronous Networked Estimation System for Continuous Time Stochastic Processes
PublikacjaIn this paper we examine an asynchronous networked estimation system for state estimation of continuous time stochastic processes. Such a system is comprised of several estimation nodes connected using a possibly incomplete communication graph. Each of the nodes uses a Kalman filter algorithm and data from a local sensor to compute local state estimates of the process under observation. It also performs data fusion of local estimates...
-
Characterizing the Performance of <span class="sc">xor</span> Games and the Shannon Capacity of Graphs
PublikacjaIn this Letter we give a set of necessary and sufficient conditions such that quantum players of a two-party xor game cannot perform any better than classical players. With any such game, we associate a graph and examine its zero-error communication capacity. This allows us to specify a broad new class of graphs for which the Shannon capacity can be calculated. The conditions also enable the parametrization of new families of games...
-
Testing the Wide-Sense Stationarity of Bandpass Signals for Underwater Acoustic Communications
PublikacjaThe Underwater Acoustic Communication (UAC) systems work in communication channels characterized by a large variety of multipath propagation conditions that can additionally change over time. Designing a reliable communication system requires knowledge of the transmission parameters of the channel. There is a need for the development of adaptive signaling schemes that would dynamically optimize the signal parameters of the physical...
-
Sodium nitrite as a corrosion inhibitor of copper in simulated cooling water
PublikacjaThe corrosion inhibition behavior of sodium nitrite (NaNO2) towards pure copper (99.95%) in simulated cooling water (SCW) was investigated by means of electrochemical impedance spectroscopy (EIS) and dynamic electrochemical impedance spectroscopy (DEIS). NaNO2 interferes with metal dissolution and reduce the corrosion rate through the formation or maintenance of inhibitive film on the metal surface. Surface morphologies illustrated...
-
Application of short-time GNSS solution geodynamical studies
PublikacjaThe paper presents the results of research related to the application of GNSS solutions in short observational periods in geodynamical investigations. Authors used the 3-hour solution appointed from hour-long interval of about 30 chosen stations on mountainous terrains from over 100 which were worked out. The main aim was to check the correctness of such solutions by the comparison with the daily ones. Some outliers in East component...
-
Interventions reducing car usage: Systematic review and meta-analysis
PublikacjaThis systematic literature review aimed to investigate the extent to which transport-related interventions induced a reduction in car use. Both qualitative synthesis and meta-analysis were employed. The synthesis included 31 original studies, while the meta-analysis included 21. Of the qualitatively synthesised studies, 74 % demonstrated that interventions were effective in reducing car use. The pooled estimates of the effects...
-
Ontology-Driven Rule-Based Model for an Extension of Information Technology Infrastructure Library Processes
PublikacjaThe aim of this study is to present the stages for building a development model to create information technology (IT) systems for IT service providers. In order to ensure the consistency of the model, a novel solution is proposed where the stages of the model's construction are controlled using ontologies dedicated to the ITIL standard. In this article, a description of models used to assess the provider organization, with particular...
-
Błędy w przedstawianiu wyników pomiarów i wartości wielkości fizycznych popełniane w pracach studenckich
PublikacjaArtykuł powstał na bazie doświadczeń zdobytych podczas pracy dydaktycznej autora jako wykładowcy i nauczyciela akademickiego prowadzącego zajęcia w Laboratorium Podstaw Metrologii. Przytoczono przykłady nieprawidłowości w przedsta-wianiu wyników pomiarów i wartości wielkości fizycznych pochodzące z prac pisemnych studentów i skonfrontowano je z zaleceniami Międzynarodowego Układu Jednostek Miar (SI), oraz polskimi aktami prawnymi.
-
Distributed state estimation using a network of asynchronous processing nodes
PublikacjaWe consider the problem of distributed state estimation of continuous-time stochastic processes using a~network of processing nodes. Each node performs measurement and estimation using the Kalman filtering technique, communicates its results to other nodes in the network, and utilizes similar results from the other nodes in its own computations. We assume that the connection graph of the network is not complete, i.e. not all nodes...
-
Global edge alliances in graphs
PublikacjaIn the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...
-
The application of nonlinear curvature sections in the turnout diverging track
PublikacjaThe paper presents the analytical method of modelling the diverging track of railway turnout with nonlinear curvature sections. These sections were used for smoothing the graph of curvature in the extreme areas of turnout. The problem of the curvature distribution was identified with the use of differential equations. The resulting solutions are of universal nature for example the ability of assuming any values of curvature at...
-
Distributed state estimation using a network of asynchronous processing nodes
PublikacjaWe consider the problem of distributed state estimation of continuous-time stochastic processes using a~network of processing nodes. Each node performs measurement and estimation using the Kalman filtering technique, communicates its results to other nodes in the network, and utilizes similar results from the other nodes in its own computations. We assume that the connection graph of the network is not complete, i.e. not all nodes...
-
Bipartite theory of graphs: outer-independent domination
PublikacjaLet $G = (V,E)$ be a bipartite graph with partite sets $X$ and $Y$. Two vertices of $X$ are $X$-adjacent if they have a common neighbor in $Y$, and they are $X$-independent otherwise. A subset $D \subseteq X$ is an $X$-outer-independent dominating set of $G$ if every vertex of $X \setminus D$ has an $X$-neighbor in $D$, and all vertices of $X \setminus D$ are pairwise $X$-independent. The $X$-outer-independent domination number...
-
Parallel Computations of Text Similarities for Categorization Task
PublikacjaIn this chapter we describe the approach to parallel implementation of similarities in high dimensional spaces. The similarities computation have been used for textual data categorization. A test datasets we create from Wikipedia articles that with their hyper references formed a graph used in our experiments. The similarities based on Euclidean distance and Cosine measure have been used to process the data using k-means algorithm....
-
Chromatographic lipophilicity determination using large volume injections of the solvents non-miscible with the mobile phase
PublikacjaA new perspective in the lipophilicity evaluation through RP-HPLC is permitted by analysis of the retentionfactor (k) obtained by injecting large volumes of test samples prepared in solvents immiscible withmobile phase. The experiment is carried out on representative groups of compounds with increasedtoxicity (mycotoxins and alkaloids) and amines with important biological activity (naturally occurringmonoamine compounds and related...
-
A brief note on entire fracture surface topography parameters for 18Ni300 maraging steel produced by LB-PBF after LCF
PublikacjaThe concept of entire fracture surface investigation is helpful in explaining fatigue phenomena. In this paper, this method has been applied for 18Ni300 maraging steel using a 3D measurement system. Before post-mortem analysis, the specimens produced by laser beam powder bed fusion (LB-PBF) were tested under low-cycle fatigue (LCF) for eight strain amplitudes in the interval 0.3% to 1.0%. The attention was placed on the relationship...
-
Accelerated large scale test set-up design in natural corrosion marine environment
PublikacjaThe standards for conducting small-scale specimen tests are well developed, but there is a lack of direct guidelines for conducting corrosion tests for large-scale specimens. The objective here is to develop a methodology which may be used in designing an accelerated corrosion test of large-scale structural components subjected to a natural corrosion marine environment. Different factors influencing corrosion degradation of steel...
-
Friction-Induced Oscillations of a Non-Asbestos Organic Pin Sliding on a Steel Disc
PublikacjaFriction-induced oscillations result in deterioration of performance of disc brakes and are generally undesired. We conduct experimental study of friction-induced oscillations in a non-asbestos organic material / steel pair used in disc brakes of motor vehicles. The tests are done by use of a pin-on-disc machine which has the pin sample supported on a deformable beam. The adjustable friction parameters are the disc velocity, contact...
-
Ionospheric scintillations computation using real-time GPS observations
PublikacjaThe following paper presents the results of quasi-real-time determination of the values of phase scintillations indices at the period of ionospheric disturbances that occurred as a consequence of the Sun flares observed on March 7 and 9, 2012. Double-frequency observations with 1-second measurement interval from the EPN (EUREF Permanent Network) network sites located at high latitudes were used for the analysis. To determine the phase...
-
Knowledge-based functional safety management using ProSIL software
PublikacjaIn the article the ProSIL software for computer aided functional safety management is presented. The software consists of three modules for the determination of the required SIL level (ProSILen) and verification of the SIL level (ProSILver). In the ProSIL the calibrated knowledge-based risk graph method for determining the required safety integrity level (SIL) of the safety functions identified in hazard analysis is implemented....
-
Big Data i 5V – nowe wyzwania w świecie danych (Big Data and 5V – New Challenges in the World of Data)
PublikacjaRodzaje danych, składające się na zbiory typu Big Data, to m.in. dane generowane przez użytkowników portali internetowych, dane opisujące transakcje dokonywane poprzez Internet, dane naukowe (biologiczne, astronomiczne, pomiary fizyczne itp.), dane generowane przez roboty w wyniku automatycznego przeszukiwania przez nie Internetu (Web mining, Web crawling), dane grafowe obrazujące powiązania pomiędzy stronami WWW itd. Zazwyczaj,...
-
Parameter values for topological chaos in the reduced Chialvo model
Dane BadawczeThe following dataset is connected with a map-based neuron model introduced by D. Chialvo (Chaos, Solitons & Fractals, 5 (3-4) 1995). The reduced version of this model is a one dimensional discrete system which describes the evolution of the membrane voltage when the value of the second variable, the recovery variable, is fixed. We have recently...
-
Visualization of short-term heart period variability with network tools as a method for quantifying autonomic drive
PublikacjaWe argue that network methods are successful in detecting nonlinear properties in the dynamics of autonomic nocturnal regulation in short-term variability. Two modes of visualization of networks constructed from RR-increments are proposed. The first is based on the handling of a state space. The state space of RR-increments can be modified by a bin size used to code a signal and by the role of a given vertex as the representation...
-
Path Loss Analysis in Off-Body Channels in Indoor Environment
PublikacjaThis temporary document describes an analysis of path loss in off-body channels in an indoor environment. The influence of body orientation and on-body antenna placement on path loss in off-body communications as well as of different bodies has been investigated. Five static scenarios, six distances between body and antenna and eight body orientations were analysed; moreover, two dynamic scenarios were investigated. The smallest...
-
Impact of the Finite Element Mesh Structure on the Solution Accuracy of a Two-Dimensional Kinematic Wave Equation
PublikacjaThe paper presents the influence of the finite element mesh structure on the accuracy of the numerical solution of a two-dimensional linear kinematic wave equation. This equation was solved using a two-level scheme for time integration and a modified finite element method with triangular elements for space discretization. The accuracy analysis of the applied scheme was performed using a modified equation method for three different...
-
A framework for risk matrix design: A case of MASS navigation risk
PublikacjaRisk matrix, a tool for visualizing risk assessment results, is essential to facilitate the risk communication and risk management in risk-based decision-making processes related to new and unexplored socio-technical systems. The use of an appropriate risk matrix is discussed in the literature, but it is overlooked for emerging technologies such as Maritime Autonomous Surface Ships (MASS). In this study, a comprehensive framework...
-
Biomechanical properties of 3D-printed bone models
PublikacjaBone lesions resulting from large traumas or cancer resections can be successfully treated by directly using synthetic materials or in combination with tissue engineering methods (hybrid). Synthetic or hybrid materials combined with bone tissue’s natural ability for regeneration and biological adaptation to the directions of loading, allow for full recovery of its biological functions. Increasing interest in new production methods...
-
Balance errors generated by numerical diffusion in the solution of non-linear open channel flow equations
PublikacjaThe paper concerns the untypical aspect of application of the dissipative numerical methods to solve nonlinear hyperbolic partial differential equations used in open channel hydraulics. It is shown that in some cases the numerical diffusion generated by the applied method of solution produces not only inaccurate solution but as well as a balance error. This error may occur even for an equation written in the conservative form not...
-
Hat problem on the cycle C4
PublikacjaThe topic of our paper is the hat problem. In that problem, each of n people is randomly tted with a blue or red hat. Then everybody can try to guess simultanously his own hat color looking at the hat colors of the other people. The team wins if at least one person 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 win. In this version every...
-
The hat problem on a union of disjoint graphs
PublikacjaThe 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 winning. In this version every player...
-
Mitigation of Fake Data Content Poisoning Attacks in NDN via Blockchain
PublikacjaAbstract—Information-centric networks struggle with content poisoning attacks (CPAs), especially their stronger form called Fake Data CPA, in which an intruder publisher uploads content signed with stolen credentials. Following an existing graphinfection based approach leveraging the constrained time when stolen credentials are useful, we design a blockchain-based mitigation scheme for Named Data Networking architectures. We postulate...
-
An O ( n log n ) algorithm for finding edge span of cacti
PublikacjaLet G=(V,E) be a nonempty graph and xi be a function. In the paper we study the computational complexity of the problem of finding vertex colorings c of G such that: (1) |c(u)-c(v)|>=xi(uv) for each edge uv of E; (2) the edge span of c, i.e. max{|c(u)-c(v)|: uv belongs to E}, is minimal. We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for...
-
Global defensive secure structures
PublikacjaLet S ⊂ V (G) for a given simple non-empty graph G. We define for any nonempty subset X of S the predicate SECG,S(X) = true iff |NG[X]∩S| ≥ |NG[X]\S|. Let H be a non-empty family of graphs such that for each vertex v ∈ V (G) there is a subgraph H of G containing v and isomorphic to a member of H. We introduce the concept of H-alliance extending the concept of global defensive secure structures. By an H-alliance in a graph G we...
-
On the partition dimension of trees
PublikacjaGiven an ordered partition Π={P1,P2,…,Pt} of the vertex set V of a connected graph G=(V,E), the partition representation of a vertex v∈V with respect to the partition Π is the vector r(v|Π)=(d(v,P1),d(v,P2),…,d(v,Pt)), where d(v,Pi) represents the distance between the vertex vv and the set Pi. A partition Π of V is a resolving partition of G if different vertices of G have different partition representations, i.e., for every...
-
Graphs with equal domination and certified domination numbers
PublikacjaA 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...
-
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...
-
Clearing directed subgraphs by mobile agents
PublikacjaWe study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(V,A) of D such that (a) S is a subset of V, (b) H is the union of k directed...
-
On the super domination number of lexicographic product graphs
PublikacjaThe neighbourhood of a vertexvof a graphGis the setN(v) of all verticesadjacent tovinG. ForD⊆V(G) we defineD=V(G)\D. A setD⊆V(G) is called a super dominating set if for every vertexu∈D, there existsv∈Dsuch thatN(v)∩D={u}. The super domination number ofGis theminimum cardinality among all super dominating sets inG. In this article weobtain closed formulas and tight bounds for the super dominating number oflexicographic product...
-
Data for meta-analysis on interversions reducing car use
Dane BadawczeThis dataset contains the results of a meta-analysis of reported interventions reducing car use. To standardise intervention effects reported in different scales, the Hedges’ g effect size measure was used (ratio of raw difference in samples’ means and pooled standard deviation). The standardised studies outcomes, along with overall outcome, were...