Filters
total: 662
-
Catalog
Search results for: GRAPH COLOURING
-
Non-relational Databases 2022/2023
e-Learning CoursesThis course discusses the three types of non-relational databases (i.e. document, graph, key-value). The course is aimed at students in the 7th semester of computer science.
-
Non-relational Databases 2023/2024
e-Learning CoursesThis course discusses the three types of non-relational databases (i.e. document, graph, key-value). The course is aimed at students in the 7th semester of computer science.
-
Non-relational Databases 2024/2025
e-Learning CoursesThis course discusses the three types of non-relational databases (i.e. document, graph, key-value). The course is aimed at students in the 7th semester of computer science.
-
Scanning networks with cactus topology
PublicationThe family of Pursuit and Evasion problems is widelystudied because of its numerous practical applications,ranging from communication protocols to cybernetic andphysical security. Calculating the search number of a graphis one of most commonly analyzed members of this problemfamily. The search number is the smallest number of mobileagents required to capture an invisible and arbitrarily fastfugitive, for instance piece of malicious...
-
Modelling of Mechatronic Systems with Distributed Parameter Components
PublicationThe paper presents an uniform, port-based approach to modelling of both lumped and distributed parameter systems. Port-based model of distributed 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 computational package for the analysis of complex...
-
An upper bound for the double outer-independent domination number of a tree
PublicationA 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 γ_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We prove...
-
Dynamics of S-unimodal maps used in population modeling.
Open Research DataS-unimodal maps are maps of the interval with negative Schwarzian derivative and having only one turning point (such that the map is increasing to the left of the turning point and decreasing to the right of it). Theory of S-unimodal maps is now a well-developed branch of discrete dynamical systems, including famous Singer theorem which implies existence...
-
Nonrelational Databases DE 2022_2023
e-Learning CoursesWithin this course the four types of non-relational databases (i.e. document, graph, key-value and column-oriented) are discussed. The course is aimed at students of the 5th semester of data engineering.
-
Continuation classes for a non-linear Leslie population model with 3 varying parameters
Open Research DataThis 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
Open Research DataThis 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),...
-
Clonal selection in discrete optimization
PublicationW rozprawie zajmujemy się efektywnymi metodami przybliżonego rozwiązywania problemów optymalizacji dyskretnej, a w szczególności algorytmami opartymi na metodzie selekcji klonalnej (SK), należącymi do kategorii sztucznych systemów immunologicznych. Techniki optymalizacji to znaczące pole badań w informatyce, a niektóre ze starszych technik, takie jak algorytmy genetyczne, symulowane wyżarzanie czy przeszukiwanie tabu, stały się...
-
A lower bound on the double outer-independent domination number of a tree
PublicationA 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ż.
PeopleComputer 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
PublicationWe 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...
-
Morse decompositions 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.
-
On the Hat Problem on the Cycle C7
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...
-
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,...
-
A survey on known values and bounds on the Shannon capacity
PublicationIn 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.
-
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...
-
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...
-
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,...
-
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...
-
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...
-
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 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...
-
The Potential of Greed for Independence
PublicationThe 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
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.
-
Latin-American Algorithms, Graphs and Optimization Symposium
Conferences -
Cologne-Twente Workshop on Graphs and Combinatorial Optimization
Conferences -
Collision-Free Network Exploration
PublicationA 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...
-
The hat problem on cycles on at least nine vertices
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 winning. In this version every player...
-
Morse decompositions for a population model with harvesting. Case Ha-Se: Harvesting adults only, equal survival rates of juveniles and adults
Open Research DataThis 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
Open Research DataThis 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
Open Research DataThis 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
Open Research DataThis 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
Open Research DataThis 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
Open Research DataThis 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.
-
Workshop on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks
Conferences -
Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
PublicationOne 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
PublicationWe 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
PublicationThe 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...
-
Counting Lattice Paths With Four Types of Steps
Publication -
Quality Control of Bacterial Extracellular Vesicles with Total Protein Content Assay, Nanoparticles Tracking Analysis, and Capillary Electrophoresis
PublicationExtracellular vesicles (EVs) were isolated from Pectobacterium zantedeschiae culturing media using direct ultracentrifugation (UC), iodixanol cushion ultracentrifugation (ICUC), and iodixanol density gradient ultracentrifugation (IDGUC) techniques. The isolates were characterized with total protein content assay (bicinchoninic acid assay, BCA), nanoparticles tracking analysis (NTA), and capillary electrophoresis (CE). A satisfactory...
-
Wordventure - cooperative wordnet editor. Architecture for lexical semantic aquisition
PublicationThis 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
PublicationThis 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.
-
Turán numbers for odd wheels
PublicationThe 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...
-
Distributed NVRAM Cache – Optimization and Evaluation with Power of Adjacency Matrix
PublicationIn 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,...
-
A Systematic Search for New Coupling Schemes of Cross-Coupled Resonator Bandpass Filters
PublicationIn this paper, a systematic approach to an extensive search for topologies of cross-coupled filters with generalized Chebyshev response is presented. The technique applies graph theory to find unique, nonisomorphic filter configurations, and tests whether a specific frequency response can be realized in a given set of topologies. The results of the search are then stored in a database of possible filter configurations.
-
Dedicated scheduling of tasks to minimize mean flow time
PublicationThis 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.