Wyszukiwarka
Filtry
wszystkich: 1292
wybranych: 1130
-
Katalog
Filtry wybranego katalogu
wyświetlamy 1000 najlepszych wyników Pomoc
Wyniki wyszukiwania dla: SHANNON CAPACITY OF GRAPHS
-
2-Coloring number revisited
Publikacja2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow...
-
A construction for the hat problem on a directed graph
PublikacjaA team of n players plays the following game. After a strategy session, each player is randomly fitted with a blue or red hat. Then, without further communication, everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. Visibility is defined by a directed graph; that is, vertices correspond to players, and a player can see each player to whom he is connected by an arc. The...
-
Application of electrochemical impedance spectroscopy to monitoring discharging process of nickel/metal hydride battery.
PublikacjaThis paper presents the possibility of applying impedance analysis to cell diagnostics. In order to obtain characteristic curves of both electrodes of a NiMH battery simultaneously, a reference electrode was added into the circuit. The authors analysed the cell under three cases, i.e. when its properties are determined only by the state of the positive electrode, only by the state of the negative electrode, or when both electrodes...
-
Dedicated scheduling of tasks to minimize mean flow time
PublikacjaThis paper investigates the complexity of scheduling biprocessor tasks on dedicated processors to minimize mean flow time. Since the general problem is strongly NP-hard, we assume some restrictions on task lengths and the structure of associated scheduling graphs. Of particular interest are acyclic graphs. In this way we identify a borderline between NP-hard and polynomially solvable special cases.
-
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.
-
Graph classes generated by Mycielskians
PublikacjaIn this paper we use the classical notion of weak Mycielskian M'(G) of a graph G and the following sequence: M'_{0}(G) =G, M'_{1}(G)=M'(G), and M'_{n}(G)=M'(M'_{n−1}(G)), to show that if G is a complete graph oforder p, then the above sequence is a generator of the class of p-colorable graphs. Similarly, using Mycielskian M(G) we show that analogously defined sequence is a generator of the class consisting of graphs for which the...
-
Chronographic Imprint of Age-Induced Alterations in Heart Rate Dynamical Organization
PublikacjaBeat-to-beat changes in the heart period are transformed into a network of increments between subsequent RR-intervals, which enables graphical descriptions of short-term heart period variability. Three types of such descriptions are considered: (1) network graphs arising from a set of vertices and directed edges, (2) contour plots of adjacency matrices A, representing the networks and transition matrices T, resulting from A, and (3)...
-
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...
-
Reliable underwater communication system for shallow coastal waters
PublikacjaThis paper presents a reliable and robust low data rate spread spectrum approach which is implemented in the acoustic underwater communication system for shallow coastal waters. It shows operation assumptions of spread spectrum techniques based on the wellknown Shannon equation. It describes two methods of spread spectrum: frequency hopping spread spectrum and direct sequence spread spectrum; their block diagram and their characteristics...
-
Computer experiments with a parallel clonal selection algorithm for the graph coloring problem
PublikacjaArtificial immune systems (AIS) are algorithms that are based on the structure and mechanisms of the vertebrate immune system. Clonal selection is a process that allows lymphocytes to launch a quick response to known pathogens and to adapt to new, previously unencountered ones. This paper presents a parallel island model algorithm based on the clonal selection principles for solving the Graph Coloring Problem. The performance of...
-
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...
-
Sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych
PublikacjaW pracy rozpatrywane są sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych. Pokazano, że w odróżnieniu od tego pierwszego, który jest łatwy, problem istnienia pokolorowań półsprawiedliwych jest NP-zupełny w szerokim zakresie parametrów grafów.
-
Relations between the domination parameters and the chromatic index of a graph
PublikacjaIn this paper we show bounds for the sum and the product of the domination parameters and the chromatic index of a graph. We alsopresent some families of graphs for which these bounds are achieved.
-
The complexity of minimum-length path decompositions
PublikacjaWe consider a bi-criteria generalization of the pathwidth problem, where, for given integers k, l and a graph G, we ask whether there exists a path decomposition P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter...
-
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....
-
Exploiting multi-interface networks: Connectivity and Cheapest Paths
PublikacjaLet G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at...
-
Properties of the triset metric for phylogenetic trees
Publikacjathe following paper presents a new polynomial time metric for unrootedphylogenetic trees (based on weighted bipartite graphs and the method ofdetermining a minimum perfect matching) and its properties. also many its properties are presented.
-
Directed percolation effects emerging from superadditivity of quantum networks
PublikacjaEntanglement-induced nonadditivity of classical communication capacity in networks consisting of quantum channels is considered. Communication lattices consisting of butterfly-type entanglement-breaking channels augmented, with some probability, by identity channels are analyzed. The capacity superadditivity in the network is manifested in directed correlated bond percolation which we consider in two flavors: simply directed and...
-
Flood Classification in a Natural Wetland for Early Spring Conditions Using Various Polarimetric SAR Methods
PublikacjaAbstract--- One of the major limitations of remote sensing flood detection is the presence of vegetation. Our study focuses on a flood classification using Radarsat-2 Quad-Pol data in a natural floodplain during leafless, dry vegetation (early spring) state. We conducted a supervised classification of a data set composed of nine polarimetric decompositions and Shannon entropy followed by the predictors' importance estimation to...
-
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...
-
Mechanizmy mocowe na rynkach energii elektrycznej
PublikacjaW artykule scharakteryzowano rozliczenia mocowe związane z dostawą energii elektrycznej. Opisano najważniejsze mechanizmy mocowe, skupiając się głównie na rozwiązaniach stosowanych w krajach europejskich. Na tym tle przedstawiono zasady funkcjonowania rynku mocy w Polsce. Omówiono wyniki pierwszych aukcji krajowych. Wskazano na możliwy wpływ funkcjonowania rynku mocy na rynek energii elektrycznej.
-
The Complexity of Zero-Visibility Cops and Robber
PublikacjaIn this work we deal with the computational complexity aspects of the zero-visibility Cops and Robber game. We provide an algorithm that computes the zero-visibility copnumber of a tree in linear time and show that the corresponding decision problem is NP-complete even for the class of starlike graphs.
-
Polynomial triset metric for unrooted phylogenetic trees
Publikacjathe following paper presents a polynomial triset metric for unrooted phylogenetic trees (based on weighted bipartite graphs and the method of determining a minimum edge cover) and its basic characteristics. also a list of further directions of research and examples of the wider use of this metric is presented.
-
Distributed graph searching with a sense of direction
PublikacjaIn this work we consider the edge searching problem for vertex-weighted graphs with arbitrarily fast and invisible fugitive. The weight function w provides for each vertex v the minimum number of searchers required to guard v, i.e., the fugitive may not pass through v without being detected only if at least w(v) searchers are present at v. This problem is a generalization of the classical edge searching problem, in which one has...
-
Scrutiny of power grids by penetrating PV energy in wind farms: a case study of the wind corridor of Jhampir, Pakistan
PublikacjaThis study examines the problems caused by intermittent renewable energy sources, especially wind farms, and suggests a different solar energy penetration strategy to improve their loading capacity. The study uses real-time data from a wind farm in Jhampir, Pakistan, to analyse and assess various aspects of grid stations connected to wind farms. Electrical Transient Analyzer Program is used to validate the results by linking...
-
Scrutiny of power grids by penetrating PV energy in wind farms: a case study of the wind corridor of Jhampir, Pakistan
PublikacjaThis study examines the problems caused by intermittent renewable energy sources, especially wind farms, and suggests a different solar energy penetration strategy to improve their loading capacity. The study uses real-time data from a wind farm in Jhampir, Pakistan, to analyse and assess various aspects of grid stations connected to wind farms. Electrical Transient Analyzer Program is used to validate the results by linking these...
-
Aspects of multistation quantum information broadcasting
PublikacjaWe study quantum information transmission over multiparty quantum channel. In particular, we show an equivalence of different capacity notions and provide a multiletter characterization of a capacity region for a general quantum channel with k senders and m receivers. We point out natural generalizations to the case of two-way classical communication capacity. (C) 2010 Elsevier B.V. All rights reserved.
-
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ą...
-
Red Algae – An Alternative Source of Carbon Material for Energy Storage Application
PublikacjaNew electrode material obtained by pyrolysis of aquatic biomass macro (red algae) soaked with glucose solution has been characterized by SEM, EDX and Raman spectroscopy. Graphitized carbon was identified by Raman spectroscopy. Galvanostatic cyclic polarization of the materials in contact with 1M LiPF6 electrolyte in EC:DMC (1:1 v/v) and Li as a counter electrode was performed. Specific capacity of the novel material was enhanced...
-
Concept of Multifactor Method and Non-Functional Requirements Solution to Increase Resilience through Functional Safety with Cybersecurity Analysis
PublikacjaIn the process of designing safety systems, an integrated approach in safety and cybersecurity analysis is necessary. The paper describes a new technique of increasing resilience through integrated analysis of functional safety and cybersecurity. It is a modeling methodology based on the combination of the multifactor method utilizing modified risk graphs, used previously for Safety Integrity Level (SIL) assessment, and the Non-Functional...
-
On minimum cost edge searching
PublikacjaWe consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not...
-
On the Characteristic Graph of a Discrete Symmetric Channel
PublikacjaWe present some characterizations of characteristic graphs of row and/or column symmetric channels. We also give a polynomial-time algorithm that decides whether there exists a discrete symmetric channel whose characteristic graph is equal to a given input graph. In addition, we show several applications of our results.
-
CRVG - a new model for wireless networks topology generation
PublikacjaThis paper presents a new model of wireless network topology generator. Its main advantage is the possibility of relatively sparse networks generation. Because no iteration is needed, the model can be used for massive generation of networks for testing. The topological properties of produced graphs place them in the class of scale free networks, resembling real ones.
-
Edge-coloring of 3-uniform hypergraphs
PublikacjaWe consider edge-colorings of 3-uniform hypergraphs which is a natural generalization of the problem of edge-colorings of graphs. Various classes of hypergraphs are discussed and we make some initial steps to establish the border between polynomial and NP-complete cases. Unfortunately, the problem appears to be computationally difficult even for relatively simple classes of hypergraphs.
-
Scheduling of compatible jobs on parallel machines
PublikacjaThe dissertation discusses the problems of scheduling compatible jobs on parallel machines. Some jobs are incompatible, which is modeled as a binary relation on the set of jobs; the relation is often modeled by an incompatibility graph. We consider two models of machines. The first model, more emphasized in the thesis, is a classical model of scheduling, where each machine does one job at time. The second one is a model of p-batching...
-
Antioxidant Interactions between Major Phenolic Compounds Found in 'Ataulfo' Mango Pulp: Chlorogenic, Gallic, Protocatechuic and Vanillic Acids
PublikacjaPhenolic compounds are known to have antioxidant capacity; however, there is little information about molecular interactions between particular phenolics found in fruits at different developmental stages. Therefore, the total antioxidant capacity of the phenolic compounds of a fruit may not correspond to the sum of individual antioxidant capacity given by antioxidants from that tissue. In this study, individual antioxidant capacity...
-
Analysis of efficiency of phosphates sorption by different granulation of selected reactive material
PublikacjaIn the light of the need to find an effective way to remove phosphorus from wastewater, studies on the suitability of sorption materials in this process should be conducted. The aim of the study was to examine the potential benefits of using selected adsorbents to reduce orthophosphates from the model solution under steady conditions. The study was conducted on a laboratory scale using synthetic wastewater with concentration of...
-
A space-efficient algorithm for computing the minimum cycle mean in a directed graph
PublikacjaAn algorithm is introduced for computing the minimum cycle mean in a strongly connected directed graph with n vertices and m arcs that requires O(n) working space. This is a considerable improvement for sparse graphs in comparison to the classical algorithms that require O(n^2) working space. The time complexity of the algorithm is still O(nm). An implementation in C++ is made publicly available at http://www.pawelpilarczyk.com/cymealg/.
-
VOLTAMMETRIC DETERMINATION OF DEOXYRIBONUCLEIC ACID PRESENCE ON A CARBON ELECTRODE
PublikacjaThis paper presents a voltammetry as a useful method to analyse DNA from different species. This electrochemical method is well know and used in different analyses. The influence of an area of working electrode and the capacity component, is shown at equals and the measurement. In voltammetry DNA measurement the capacity component is very important and must be taken into consideration. All mathematical analyses were verify at laboratory.
-
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...
-
Purely quantum superadditivity of classical capacities of quantum multiple access channels
PublikacjaWe are studying classical capacities of quantum memoryless multiaccess channels in geometric terms and we are revealing a break of additivity of the Holevo-like capacity. This effect is a purely quantum mechanical one, since, as we point out, the capacity regions of all classical memoryless multiaccess channels are additive. It is the first such effect revealed in the field of classical information transmission via quantum channels.
-
On zero-error codes produced by greedy algorithms
PublikacjaWe present two greedy algorithms that determine zero-error codes and lower bounds on the zero-error capacity. These algorithms have many advantages, e.g., they do not store a whole product graph in a computer memory and they use the so-called distributions in all dimensions to get better approximations of the zero-error capacity. We also show an additional application of our algorithms.
-
The complexity of zero-visibility cops and robber
PublikacjaWe consider the zero-visibility cops & robber game restricted to trees. We produce a characterisation of trees of copnumber k and We consider the computational complexity of the zero-visibility Cops and Robber game. We present a heavily modified version of an already-existing algorithm that computes the zero-visibility copnumber of a tree in linear time and we show that the corresponding decision problem is NP-complete on a nontrivial...
-
INTER-LAYER SHARING OF BACKUP PATH CAPACITIES PROVIDING FAST SERVICE RECOVERY IN IP-MPLS/WDM NETWORKS
PublikacjaIn this paper, we investigate the issue of providing the transmission continuity in IP-MPLS/WDM networks in the presence of failures of nodes/links. Special focus is put on assuring fast restoration of flows affected after a failure in a scenario assuming sharing the backup path capacities in order to decrease the overall bandwidth consumption. In particular, we propose a new approach to inter-layer sharing of link capacity reserved...
-
Schemes of transmission of classical information via quantum channels with many senders: Discrete- and continuous-variable cases
PublikacjaSuperadditivity effects in the classical capacity of discrete multiaccess channels and continuous variable (CV) Gaussian MACs are analyzed. Several examples of the manifestation of superadditivity in the discrete case are provided, including, in particular, a channel which is fully symmetric with respect to all senders. Furthermore, we consider a class of channels for which input entanglement across more than two copies of the...
-
Electrochemical Characterization of Gelatine Derived Ceramics
PublikacjaNew materials obtained by pyrolysis of gelatine (G) and poly(1,2-dimethylsilazane) (PSN) (weight ratio: G/PSN 70/30) at temperatures 700 and 900 °C were characterized by SEM and Raman spectroscopy. The presence of ceramics influences on the cluster size of the materials. Electrochemical tests were performed by cyclic voltammetry and galvanostatic cyclic polarization. The capacity of G/PSN was 464 and 527 mAh/g for materials pyrolysed...
-
Analiza porównawcza metod obliczania przebicia
PublikacjaW artykule przedstawiono analizę porównawczą wybranych normowych metod wyznaczania nośności na przebicie konstrukcji płytowo-słupowej. Przeanalizowano trzy normowe sposoby wyznaczania nośności na przebicie.Wykonane obliczenia pozwoliły na wskazanie różnic w wyznaczonych wartościach nośności płyty na przebicie w konstrukcji płytowo-słupowej.
-
Effect of Base-Connection Strength and Ductility on the Seismic Performance of Steel Moment-Resisting Frames
PublikacjaColumn-base connections in steel moment-resisting frames (SMFs) in seismic regions are commonly designed to develop the capacity of adjoining column with an intent to develop a plastic hinge in the column member, rather than in the connection (i.e., a strong-base design). Recent research has shown base connections to possess high ductility, indicating that this practice may be not only expensive but also unnecessary. This suggests...
-
Przepustowość przepustu niezatopionego
PublikacjaPodczas przepływu w warunkach niezatopionego wlotu i wylotu w przewodzie przepustu woda tworzyć będzie swobodne zwierciadło. Przepływ bezciśnieniowy w przewodzie przepustu może wystąpić również w warunkach zatopionego wlotu. W pracy porównano wyniki obliczeń przepustowości całego przepustu i samego przewodu o przekroju kołowym i kwadratowym. W warunkach spokojnego ruchu wody, przy braku spiętrzenia na wylocie, o przepustowości...
-
Parallel tabu search for graph coloring problem
PublikacjaTabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of patallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experimental results are based on graphs available from the DIMACS...