Filtry
wszystkich: 653
-
Katalog
- Publikacje 528 wyników po odfiltrowaniu
- Czasopisma 9 wyników po odfiltrowaniu
- Konferencje 19 wyników po odfiltrowaniu
- Osoby 9 wyników po odfiltrowaniu
- Wynalazki 1 wyników po odfiltrowaniu
- Projekty 1 wyników po odfiltrowaniu
- Kursy Online 4 wyników po odfiltrowaniu
- Wydarzenia 2 wyników po odfiltrowaniu
- Dane Badawcze 80 wyników po odfiltrowaniu
Wyniki wyszukiwania dla: BIPARTITE GRAPH
-
Nonadditivity of quantum and classical capacities for entanglement breaking multiple-access channels and the butterfly network
PublikacjaWe analyze quantum network primitives which are entanglement breaking. We show superadditivity of quantum and classical capacity regions for quantum multiple-access channels and the quantum butterfly network. Since the effects are especially visible at high noise they suggest that quantum information effects may be particularly helpful in the case of the networks with occasional high noise rates. The present effects provide a qualitative...
-
Total chromatic sum for trees
PublikacjaThe total chromatic sum of a graph is the minimum sum of colors (natural numbers) taken over all proper colorings of vertices and edges of a graph. We provide infinite families of trees for which the minimum number of colors to achieve the total chromatic sum is equal to the total chromatic number. We construct infinite families of trees for which these numbers are not equal, disproving the conjecture from 2012.
-
Continuation classes for a non-linear Leslie population model with 3 varying parameters
Dane BadawczeThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper "A database schema for the analysis of global dynamics of multiparameter systems" by Z. Arai, W. Kalies, H. Kokubu, K. Mischaikow, H. Oka, P. Pilarczyk, published in SIAM Journal on Applied Dynamical Systems (SIADS),...
-
Continuation classes for a non-linear Leslie population model with 2 varying parameters
Dane BadawczeThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper "A database schema for the analysis of global dynamics of multiparameter systems" by Z. Arai, W. Kalies, H. Kokubu, K. Mischaikow, H. Oka, P. Pilarczyk, published in SIAM Journal on Applied Dynamical Systems (SIADS),...
-
A lower bound on the double outer-independent domination number of a tree
PublikacjaA vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)D is independent. The double outer-independent domination number of a graph G, denoted by gamma_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We...
-
Krzysztof Kutt dr inż.
OsobyComputer scientist and psychologist trying to combine expertise from both disciplines into something cool. My research activity focuses on the development of affective HCI/BCI interfaces (based on multimodal fusion of signals and contextual data), methods for processing sensory data (including semantization of such data) and the development of knowledge-based systems (in particular knowledge graphs and semantic web systems).
-
Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots
PublikacjaWe study two variants of delivery problems for mobile robots sharing energy. Each mobile robot can store at any given moment at most two units of energy, and whenever two robots are at the same location, they can transfer energy between each other, respecting the maximum capacity. The robots operate in a simple graph and initially each robot has two units of energy. A single edge traversal by an robot reduces its energy by one...
-
Preface of guest editors
PublikacjaA special issue of Discussiones Mathematice Graph Theory (DMGT) is dedicated to selected papers presented at the 12th Workshop on Graph Theory: Colourings, Independence and Domination (CID) held on 16-21 September 2007 in Karpacz, Poland. It continues a series of international workshops: 1993-1997 in Lubiatów, 1998-2001 in Gronów, 2003 and 2005 in Karpacz. About 70 participants formed the audience of six invited lectures and 68...
-
Morse decompositions for a two-patch vaccination model
Dane BadawczeThis 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.
-
On the Hat Problem on the Cycle C7
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 a win. In this version every player can...
-
NO-BROADCASTING OF NON-SIGNALLING BOXES VIA OPERATIONS WHICH TRANSFORM LOCAL BOXES INTO LOCAL ONES
PublikacjaWe deal with families of probability distributions satisfying non-signalling condition, called non-signalling boxes and consider a class of operations that transform local boxes into local ones (the one that admit LHV model). We prove that any operation from this class cannot broadcast a bipartite non-local box with 2 binary inputs and outputs. We consider a function called anti-Robustness which can not decrease under these operations....
-
Collective Uncertainty Entanglement Test
PublikacjaFor a given pure state of a composite quantum system we analyze the product of its projections onto aset of locally orthogonal separable pure states. We derive a bound for this product analogous to theentropic uncertainty relations. For bipartite systems the bound is saturated for maximally entangled statesand it allows us to construct a family of entanglement measures, we shall call collectibility. As thesequantities are experimentally...
-
A lower bound on the total outer-independent domination number of a tree
PublikacjaA 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,...
-
A survey on known values and bounds on the Shannon capacity
PublikacjaIn this survey we present exact values and bounds on the Shannon capacity for different classes of graphs, for example for regular graphs and Kneser graphs. Additionally, we show a relation between Ramsey numbers and Shannon capacity.
-
Entanglement and Nonlocality are Inequivalent for Any Number of Parties
PublikacjaUnderstanding the relation between nonlocality and entanglement is one of the fundamental problems in quantum physics. In the bipartite case, it is known that these two phenomena are inequivalent, as there exist entangled states of two parties that do not violate any Bell inequality. However, except for a single example of an entangled three-qubit state that has a local model, almost nothing is known about such a relation in multipartite...
-
All Nonclassical Correlations Can Be Activated into Distillable Entanglement
PublikacjaWe devise a protocol in which general nonclassical multipartite correlations produce a physically relevant effect, leading to the creation of bipartite entanglement. In particular, we show that the relative entropy of quantumness, which measures all nonclassical correlations among subsystems of a quantum system, is equivalent to and can be operationally interpreted as the minimum distillable entanglement generated between the system...
-
Dynamics of quantum entanglement
PublikacjaA model of discrete dynamics of entanglement of a bipartite quantum state is considered. It involves a global unitary dynamics of the system and periodic actions of local bistochastic or decaying channel. For initially pure states the decay of entanglement is accompanied by an increase of von Neumann entropy of the system. We observe and discuss revivals of entanglement due to unitary interaction of subsystems. For some mixed states...
-
Bounds on the vertex-edge domination number of a tree
PublikacjaA 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...
-
Finding small-width connected path decompositions in polynomial time
PublikacjaA 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
PublikacjaThe 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...
-
An upper bound on the 2-outer-independent domination number of a tree
PublikacjaA 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
PublikacjaA 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,...
-
Weighted 2-sections and hypergraph reconstruction
PublikacjaIn 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...
-
A Note on Shannon Capacity for Invariant and Evolving Channels
PublikacjaIn 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 upper bound on the total outer-independent domination number of a tree
PublikacjaA 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...
-
Simple sufficient condition for subspace to be completely or genuinely entangled
PublikacjaWe introduce a simple sufficient criterion, which allows one to tell whether a subspace of a bipartite or multipartite Hilbert space is entangled. The main ingredient of our criterion is a bound on the minimal entanglement of a subspace in terms of entanglement of vectors spanning that subspace expressed for geometrical measures of entanglement. The criterion is applicable to both completely and genuinely entangled subspaces. We...
-
The Potential of Greed for Independence
PublikacjaThe well-known lower bound on the independence number of a graph due to Caro and Wei can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so-called potential functions p(G) : V(G) -> N_0 defined on the vertex set of a graph G for which suitably...
-
Continuation classes for a two-patch vaccination model
Dane BadawczeThis 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.
-
Thermodynamical approach to quantifying quantum correlations
PublikacjaWe consider the amount of work which can be extracted from a heat bath using a bipartite state ρ shared by two parties. In general it is less then the amount of work extractable when one party is in possession of the entire state. We derive bounds for this “work deficit” and calculate it explicitly for a number of different cases. In particuar, for pure states the work deficit is exactly equal to the distillable entanglement of...
-
Latin-American Algorithms, Graphs and Optimization Symposium
Konferencje -
Cologne-Twente Workshop on Graphs and Combinatorial Optimization
Konferencje -
Preface
PublikacjaThis special issue of Discussiones Mathematice Graph Theory (DMGT) is dedicated to selected papers presented at the 13th Workshop on Graph Theory: Colourings, Independence and Domination (CID) held on 18-23 September 2009 in Szklarska Poręba, Poland. It continues a series of international workshops: 1993-1997 in Lubiatów, 1998-2001 in Gronów, and 2003-2007 in Karpacz. The meeting was organized by the Faculty of Mathematics, Computer...
-
Collision-Free Network Exploration
PublikacjaA set of mobile agents is placed at different nodes of a n-node network. The agents synchronously move along the network edges in a collision-free way, i.e., in no round may two agents occupy the same node. In each round, an agent may choose to stay at its currently occupied node or to move to one of its neighbors. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest possible...
-
Morse decompositions for a population model with harvesting. Case Ha-Se: Harvesting adults only, equal survival rates of juveniles and adults
Dane BadawczeThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper "Global dynamics in a stage-structured discrete population model with harvesting" by E. Liz and P. Pilarczyk: Journal of Theoretical Biology, Vol. 297 (2012), pp. 148–165, doi: 10.1016/j.jtbi.2011.12.012.
-
Morse decompositions for a population model with harvesting. Case He-S1: Equal harvesting of juveniles and adults, survival rates of juveniles and adults add up to 1
Dane BadawczeThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper "Global dynamics in a stage-structured discrete population model with harvesting" by E. Liz and P. Pilarczyk: Journal of Theoretical Biology, Vol. 297 (2012), pp. 148–165, doi: 10.1016/j.jtbi.2011.12.012.
-
Morse decompositions for a population model with harvesting. Case Ha-S1: Harvesting adults only, survival rates of juveniles and adults add up to 1
Dane BadawczeThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper "Global dynamics in a stage-structured discrete population model with harvesting" by E. Liz and P. Pilarczyk: Journal of Theoretical Biology, Vol. 297 (2012), pp. 148–165, doi: 10.1016/j.jtbi.2011.12.012.
-
Morse decompositions for a population model with harvesting. Case He-Se: Equal harvesting and equal survival rates of juveniles and adults
Dane BadawczeThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper "Global dynamics in a stage-structured discrete population model with harvesting" by E. Liz and P. Pilarczyk: Journal of Theoretical Biology, Vol. 297 (2012), pp. 148–165, doi: 10.1016/j.jtbi.2011.12.012.
-
Morse decompositions for a population model with harvesting. Case Hj-Se: Harvesting juveniles only, equal survival rates of juveniles and adults
Dane BadawczeThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper "Global dynamics in a stage-structured discrete population model with harvesting" by E. Liz and P. Pilarczyk: Journal of Theoretical Biology, Vol. 297 (2012), pp. 148–165, doi: 10.1016/j.jtbi.2011.12.012.
-
Morse decompositions for a population model with harvesting. Case Hj-S1: Harvesting juveniles only, survival rates of juveniles and adults add up to 1
Dane BadawczeThis dataset contains selected results of rigorous numerical computations conducted in the framework of the research described in the paper "Global dynamics in a stage-structured discrete population model with harvesting" by E. Liz and P. Pilarczyk: Journal of Theoretical Biology, Vol. 297 (2012), pp. 148–165, doi: 10.1016/j.jtbi.2011.12.012.
-
The hat problem on cycles on at least nine vertices
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...
-
Workshop on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks
Konferencje -
Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
PublikacjaOne of the recently considered models of robot-based computing makes use of identical, memoryless mobile units placed in nodes of an anonymous graph. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of the nodes adjacent to its current position (Compute), and in the latter case makes an instantaneous...
-
A NOTE ON ON-LINE RAMSEY NUMBERS FOR QUADRILATERALS
PublikacjaWe consider on-line Ramsey numbers defined by a game played between two players, Builder and Painter. In each round Builder draws an the edge and Painter colors it either red or blue, as it appears. Builder’s goal is to force Painter to create a monochromatic copy of a fixed graph H in as few rounds as possible. The minimum number of rounds (assuming both players play perfectly) is the on-line Ramsey number \widetilde{r}(H) of...
-
Necessary and Sufficient Condition for State-Independent Contextual Measurement Scenarios
PublikacjaThe problem of identifying measurement scenarios capable of revealing state-independent contextuality in a given Hilbert space dimension is considered. We begin by showing that for any given dimension d and any measurement scenario consisting of projective measurements, (i) the measure of contextuality of a quantum state is entirely determined by its spectrum, so that pure and maximally mixed states represent the two extremes...
-
Towards the boundary between easy and hard control problems in multicast Clos networks
PublikacjaIn this article we study 3-stage Clos networks with multicast calls in general and 2-cast calls, in particular. We investigate various sizes of input and output switches and discuss some routing problems involved in blocking states. To express our results in a formal way we introduce a model of hypergraph edge-coloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially...
-
Counting Lattice Paths With Four Types of Steps
Publikacja -
Wordventure - cooperative wordnet editor. Architecture for lexical semantic aquisition
PublikacjaThis article presents architecture for acquiring lexical semanticsin a collaborative approach paradigm. The system enablesfunctionality for editing semantic networks in a wikipedia-like style. The core of the system is a user-friendly interface based on interactive graph navigation.It has been used for semantic network presentation,and brings simultaneously modification functionality.
-
WordVenture - COOPERATIVE WordNet EDITOR Architecture for Lexical Semantic Acquisition
PublikacjaThis article presents architecture for acquiring lexical semantics in a collaborative approach paradigm. The system enables functionality for editing semantic networks in a wikipedia-like style. The core of the system is a user-friendly interface based on interactive graph navigation. It has been used for semantic network presentation, and brings simultaneously modification functionality.
-
Distributed NVRAM Cache – Optimization and Evaluation with Power of Adjacency Matrix
PublikacjaIn this paper we build on our previously proposed MPI I/O NVRAM distributed cache for high performance computing. In each cluster node it incorporates NVRAMs which are used as an intermediate cache layer between an application and a file for fast read/write operations supported through wrappers of MPI I/O functions. In this paper we propose optimizations of the solution including handling of write requests with a synchronous mode,...
-
Turán numbers for odd wheels
PublikacjaThe Turán number ex(n,G) is the maximum number of edges in any n-vertex graph that does not contain a subgraph isomorphic to G. A wheel W_n is a graph on n vertices obtained from a C_{n−1} by adding one vertex w and making w adjacent to all vertices of the C_{n−1}. We obtain two exact values for small wheels: ex(n,W_5)=\lfloor n^2/4+n/2\rfloor, ex(n,W_7)=\lfloor n^2/4+n/2+1 \rfloor. Given that ex(n,W_6) is already known, this...