Filters
total: 605
-
Catalog
Search results for: GRAPH CHROMATIC GAME
-
A space-efficient algorithm for computing the minimum cycle mean in a directed graph
PublicationAn 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/.
-
Computer experiments with a parallel clonal selection algorithm for the graph coloring problem
PublicationArtificial 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...
-
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines
PublicationIn this paper we consider a problem of job scheduling on parallel machines with a presence of incompatibilities between jobs. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. Our research stems from the works of Bodlaender, Jansen, and Woeginger (1994) and Bodlaender and Jansen (1993). In particular, we pursue the...
-
Comparison of reproduction strategies in genetic algorithm approach to graph searching
Publicationgenetic algorithms (ga) are a well-known tool used to obtain approximate solutions to optimization problems. successful application of genetic algorithm in solving given problem is largely dependant on selecting appropriate genetic operators. selection, mutation and crossover techniques play a fundamental role in both time needed to obtain results and their accuracy. in this paper we focus on applying genetic algorithms in calculating...
-
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms
PublicationIn this paper, the problem of scheduling on parallel machines with a presence of incompatibilities between jobs is considered. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. The paper provides several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality:...
-
A repeated game formulation of network embedded coding for multicast resilience in extreme conditions
PublicationComputer networks and data sharing applications are vital for our current society and fundamental for any available ICT solution, so that networking is considered as one of the key critical infrastructures and its correct behavior should be always enforced, even in case of disasters or severe execution conditions. Resilience is a strongly demanding nonfunctional requirement for current computer networks, and one of the key factors...
-
Koala graph coloring library: an open graph coloring library for real-world applications
PublicationPomimo intensywnej pracy naukowej na polu kolorowania grafów, nie jest znana kompletna i dedykowana biblioteka programistyczna. Celem artykułu jest zaproponowanie architektury takiej biblioteki. Celem jest spełnienie oczekiwań wypływających z rzeczywistych zastosowań, w szczególności spełnienie potrzeb wydajnościowych. Zaimplementowano szereg algorytmów cheurystycznego kolorowania grafów. Przyjętym językiem programowania jest C++....
-
Forwarding and optical indices of a graph
PublicationW pracy rozstrzygnięto dwa problemy dotyczące komunikacji wszyscy-do-wszystkich w grafach. Stwierdzono, że dla wersji skierowanej problemu parametry ''pi'' (maksymalne obciążenie krawędzi) i ''w'' (parametr chromatyczny) nie muszą być w ogólności sobie równe. Dla wersji nieskierowanej problemu pokazano, że wyznaczenie wartości zarówno ''pi'', jak i ''w'', jest w ogólności problemem NP-trudnym.
-
Mixed graph edge coloring
PublicationW pracy rozważany jest problem kolorowania krawędzi grafu mieszanego, tj. grafu zawierającego zawiero skierowane, jak i nieskierowane krawędzie. Motywację do badań stanowią zagadnienia komunikacyjne z zakresu szeregowania zadań.
-
Graph models of clos networks
Publication...
-
Interval incidence graph coloring
PublicationIn this paper we introduce a concept of interval incidence coloring of graphs and survey its general properties including lower and upper bounds on the number of colors. Our main focus is to determine the exact value of the interval incidence coloring number χii for selected classes of graphs, i.e. paths, cycles, stars, wheels, fans, necklaces, complete graphs and complete k-partite graphs. We also study the complexity of the...
-
On a Recurrence Arising in Graph Compression
PublicationIn a recently proposed graphical compression algorithm by Choi and Szpankowski (2012), the following tree arose in the course of the analysis. The root contains n balls that are consequently distributed between two subtrees according to a simple rule: In each step, all balls independently move down to the left subtree (say with probability p) or the right subtree (with probability 1p). A new node is created as long as...
-
Parallel scheduling by graph ranking
PublicationNr dokum.: 73017Praca dotyczy jednego z nieklasycznych modeli kolorowania grafów - uporządkowanego kolorowania. Celem było uzyskanie wyników, które mogo być wykorzystane w praktycznych zastosowaniach tego modelu, do których należą: równoległe przetwarzanie zapytań w relacyjnych bazach danych, równoległa faktoryzacja macierzy metodą Choleskiego, równoległa asemblacja produktu z jego części składowych. W pracy wskazano uogólnienia...
-
Application of crowdfunding to video game projects financing
Publication -
Wireless Multihoming Modeled as a Multi-WLAN Game
PublicationZbadano strategie wieloetapowe dostępu do medium transmisyjnego oparte na tzw. wypłatach wirtualnych, biorąc pod uwagę wybór sieci lokalnej oraz stopień agresji konfiguracji protokołu MAC. Zakładano obecność stacji-agresora o idealnie predykcyjnej strategii dostępu. Wykazano możliwość zniechęcania takiego agresora za cenę niewielkiego spadku wydajności sieci.
-
Neural Graph Collaborative Filtering: Analysis of Possibilities on Diverse Datasets
PublicationThis paper continues the work by Wang et al. [17]. Its goal is to verify the robustness of the NGCF (Neural Graph Collaborative Filtering) technique by assessing its ability to generalize across different datasets. To achieve this, we first replicated the experiments conducted by Wang et al. [17] to ensure that their replication package is functional. We received sligthly better results for ndcg@20 and somewhat poorer results for...
-
Wojciech Wojnowski dr inż.
PeopleUkończył V Liceum Ogólnokształcące w Gdańsku w klasie o profilu matematyczno-fizycznym z wykładowym językiem angielskim. W 2009 roku rozpoczął studia na Wydziale Chemicznym PG na kierunku technologia chemiczna, uzyskując w 2012 roku tytuł inżyniera, a w 2013 tytuł magistra. W latach 2013–2015 studiował sinologię na Uniwersytecie w Nankinie dzięki uzyskaniu Stypendium Rządu ChRL. Po powrocie do Polski w 2015 roku rozpoczął studia...
-
Simulation Game BiM 2022/2023
e-Learning Courses -
Emotion Recognition from Physiological Channels Using Graph Neural Network
PublicationIn recent years, a number of new research papers have emerged on the application of neural networks in affective computing. One of the newest trends observed is the utilization of graph neural networks (GNNs) to recognize emotions. The study presented in the paper follows this trend. Within the work, GraphSleepNet (a GNN for classifying the stages of sleep) was adjusted for emotion recognition and validated for this purpose. The...
-
The outer-connected domination number of a graph
PublicationW pracy została zdefiniowana liczba dominowania zewnętrznie spójnego i przedstawiono jej podstawowe własności.
-
On the total restrained domination number of a graph
PublicationW pracy przedstawione są ograniczenia i własności liczby dominowania podwójnie totalnego.
-
The task graph assignment for KASKADA platform
PublicationArtykuł opisuje model obliczeniowy wykorzystany w platformie KASKADA. Opiera się on na dwóch podstawowych elementach: węzłach klastra obliczeniowego oraz grafie zadań. Przeanalizowane zostały algorytmy przydzielania węzłów obliczeniowych dla zadań w zależności od kryteriów: minimalizacja fragmentacji klastra i minimalizacja opóźnienia przetwarzania danych. Zostały przedstawione wyniki symulacji opisanych algorytmów oraz ich...
-
On the doubly connected domination number of a graph
PublicationW pracy została zdefiniowana liczba dominowania podwójnie spójnego i przedstawiono jej podstawowe własności.
-
On greedy graph coloring in the distributed model
PublicationArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Zaprezentowano nowy probabilistyczny algorytm dający w wyniku pokolorowanie LF. Udowodniono, że jakakolwiek rozproszona implementacja LF wymaga co najmniej D rund, gdzie D jest maksymalnym stopniem wierzchołka w grafie.
-
Organizational innovativeness and coopetition: a study of video game developers
Publication -
Game theory, as a way for integrating of ship control systems
PublicationReferat przedstawia koncepcję wykorzystania algorytmów zastosowanych w teorii gier do zintegrowania układów sterowania statków, takich jak układ sterowania kursu i trajektorii statku, układ sterowania napędu statku, układ sterowania stabilizacji kołysań bocznych statku, itp. Jest to koncepcja oryginalna.
-
Inorganic membrane: a game changer for gas separation and purification
PublicationThis review explores the advancements and remaining challenges in inorganic membrane science, particularly focusing on their potential for industrial applications. It delves into the fundamental principles of inorganic membrane design, fabrication, and characterization techniques. The review also critically analyzes key challenges faced by inorganic membranes, such as physical aging, plasticization, defective formation, and fouling....
-
Chromatic Scheduling of 1- and 2-Processor UET Tasks on Dedicated Machines with Availability Constraints
Publication -
Chromatic scheduling of 1- and 2-processor uet tasks on dedicated machines with availability constraints.
PublicationRozważono uogólnienie klasycznego szeregowania jednostkowych zadań jedno- i dwuprocesorowych na maszynach dedykowanych. Przyjęty model pozwala na naturalne wprowadzenie wszystkich klasycznych kryteriów optymalizacyjnych dla harmonogramów. Zaproponowano algorytmy wielomianowe dla systemów rzadkich.
-
International Game Theory Review
Journals -
INTERNATIONAL JOURNAL OF GAME THEORY
Journals -
Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph
PublicationA vertex cover of a graph G = (V, E) is a set X ⊂ V such that each edge of G is incident to at least one vertex of X. The ve cardinality of a vertex cover of G. A dominating set D ⊆ V is a weakly connected dominating set of G if the subgraph G[D]w = (N[D], Ew) weakly induced by D, is connected, where Ew is the set of all edges having at least one vertex in D. The weakly connected domination number γw(G) of G is the minimum cardinality...
-
A better practical algorithm for distributed graph coloring
Publication -
Interval vertex-coloring of a graph with forbidden colors
Publication -
Interval Vertex-Coloring of a Graph With Forbidden Colors
Publication -
The smallest hard-to-color graph for algorithm DSATUR
Publication -
Interval edge coloring of a graph with forbidden colors
Publication -
The smallest hard-to-color graph for the SL algorithm
Publication -
Graph Approach to the Computation of the Homology of Continuous Maps
Publication -
Graph decomposition for improving memoryless periodic exploration
PublicationW ostatnich latach często badanym problem jest eksploracja anonimowych grafów z lokalnymi etykietami portów przy każdym wierzchołku. Niedawno pokazano [Czyzowicz et al., Proc. SIROCCO'09], że dla każdego grafu istnieje poetykietowanie prowadzące do eksploracji przez automat bezpamięciowy z okresem co najwyżej 13n/3. W niniejszej pracy poprawiamy to ograniczenie do 4n-2, stosując całkowicie nową technikę dekompozycji grafu.
-
Efficient parallel query processing by graph ranking
PublicationW artykule analizujemy przybliżony algorytm dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym, co znajduje zastosowanie w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie uporządkowanego indeksu chromatycznego drzewa, które prowadzi do uzyskania lepszej funkcji dobroci wspomnianego algorytmu.
-
Distributed largest-first algorithm for graph coloring.
PublicationW artykule zaprezentowano rozproszony, probabilistyczny algorytm kolorowania grafów. Kolorowanie uzyskane jest optymalne lub prawie optymalne dla takich klas grafów jak koła dwudzielne, gąsienice czy korony. Udowodniono, że algorytm ten działa w czasie O(D^2 log n) rund dla dowolnego grafu n wierzchołkowegoo stopniu maksymalnym D.
-
An experimental study of distributed algorithms for graph coloring.
PublicationW pracy podano algorytm rozproszonego kolorowania grafówi porównano ze znanym wcześniej algorytmem.
-
Packing three-vertex paths in a subcubic graph
PublicationW pracy rozważany jest problem pakowania scieżek P3 w grafach podkubicznych, pokazano oszacowania dolne na ilość ścieżek w zależności od stopnia spójności grafu oraz minimalnego stopnia.
-
Chromatic monitoring technique for thickness measurementof thin transparent films.IV Workshopon Atomic and Molecular Physics.
PublicationW pracy opisano nową technikę monitorowania grubości cienkich warstw podczas procesu ich syntezy. Jest to optyczna metoda oparta na zdegenerowanej analizie widmowej tzw. modulacji chromatycznej. Umożliwia ona precyzyjny ciągły pomiar zmian grubości wzrastających warstw stosowanych w optyce.
-
Graph Neural Networks and Structural Information on Ionic Liquids: A Cheminformatics Study on Molecular Physicochemical Property Prediction
PublicationIonic liquids (ILs) provide a promising solution in many industrial applications, such as solvents, absorbents, electrolytes, catalysts, lubricants, and many others. However, due to the enormous variety of their structures, uncovering or designing those with optimal attributes requires expensive and exhaustive simulations and experiments. For these reasons, searching for an efficient theoretical tool for finding the relationship...
-
A game-theoretic study of CSMA/CA under a backoff attack
PublicationAnalizowany jest rozdział pasma realizowany przez protokół CSMA/CA w obecności anonimowych stacji egoistycznych, atakujących wykładniczy mechanizm odczekania. Przy założeniu ruchu nasycającego sieć pokazuje się, że powstaje w ten sposób niekooperacyjna gra o strukturze wypłat wieloosobowego dylematu więźnia. Wykorzystując własności macierzy wypłat zaproponowano strategię dla odpowiedniej gry wieloetapowej, zapewniającą asymptotyczne...
-
Electronic Journal of Graph Theory and Applications
Journals -
CAUSALITY IN MODELS OF THERMAL PROCESSES IN SHIP ENGINE ROOMS WITH THE USE OF BOND GRAPH (BG) METHOD
PublicationWith a single approach to modeling elements of different physical nature, the method of Bond Graph (BG) is particularly well suited for modeling energy systems consisting of mechanical, thermal, electrical and hydraulic elements that operate in the power system engine room. The paper refers to the earlier presented new concept of thermal process modeling using the BG method. The authors own suggestions for determining causality...
-
Management Simulation Game - LATO 2022/2023 - DZIENNE
e-Learning Courses