Wyszukiwarka
Filtry
wszystkich: 488
-
Katalog
Wyniki wyszukiwania dla: EQUITABLE GRAPH COLORING
-
Multi-agent graph searching and exploration algorithms
PublikacjaA team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents...
-
Product Graph Invariants with Applications in the Theory of Information
PublikacjaThere are a large number of graph invariants. In the paper, we consider some of them, e.g. the independence and chromatic numbers. It is well know that we cannot efficiently calculate these numbers for arbitrary graphs. In the paper we present relations between these invariants and concepts from the theory of information. Concepts such as source coding and transmission over a noisy channel with zero probability of error are modeled...
-
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...
-
KOALA Graph Theory Internet Service
PublikacjaKOALA has been created with the idea of C++ library templates, implementing a broad set of procedures in the fields of algorithmic graph theory and network problems in discreate optimization. During the C2NIWA project, a library has been greatly ectended, the code refactored and enclosed with the internet service available in the public repository of thr project. Today it contains interconnected educational materials in the form...
-
New potential functions for greedy independence and coloring
PublikacjaA potential function $f_G$ of a finite, simple and undirected graph $G=(V,E)$ is an arbitrary function $f_G : V(G) \rightarrow \mathbb{N}_0$ that assigns a nonnegative integer to every vertex of a graph $G$. In this paper we define the iterative process of computing the step potential function $q_G$ such that $q_G(v)\leq d_G(v)$ for all $v\in V(G)$. We use this function in the development of new Caro-Wei-type and Brooks-type...
-
Optimal edge-coloring with edge rate constraints
PublikacjaWe consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable....
-
Pawlak's flow graph extensions for video surveillance systems
PublikacjaThe idea of the Pawlak's flow graphs is applicable to many problems in various fields related to decision algorithms or data mining. The flow graphs can be used also in the video surveillance systems. Especially in distributed multi-camera systems which are problematic to be handled by human operators because of their limited perception. In such systems automated video analysis needs to be implemented. Important part of this analysis...
-
Zero-Visibility Cops and Robber Game on a Graph
PublikacjaWe examine the zero-visibility cops and robber graph searching model, which differs from the classical cops & robber game in one way: the robber is invisible. We show that this model is not monotonic. We also provide bounds on both the zero-visibility copnumber and monotonic zero-visibility copnumber in terms of the pathwidth.
-
Modeling the impact of surface currents in a harbor using graph theory
PublikacjaEnsuring security in a harbor requires research into its infrastructure using spatial environmental data. This paper presents a methodology that defines the design of a graph for modeling the interactions between surface currents and moving objects. Combining this graph with port charts that integrate electronic navigation charts with coastal orthophotographs allows us to perform a multidimensional analysis. In addition, the complete...
-
Characterizing the Scalability of Graph Convolutional Networks on Intel® PIUMA
PublikacjaLarge-scale Graph Convolutional Network (GCN) inference on traditional CPU/GPU systems is challenging due to a large memory footprint, sparse computational patterns, and irregular memory accesses with poor locality. Intel’s Programmable Integrated Unffied Memory Architecture (PIUMA) is designed to address these challenges for graph analytics. In this paper, a detailed characterization of GCNs is presented using the Open-Graph Benchmark...
-
Weakly convex domination subdivision number of a graph
PublikacjaA set X is weakly convex in G if for any two vertices a; b \in X there exists an ab–geodesic such that all of its vertices belong to X. A set X \subset V is a weakly convex dominating set if X is weakly convex and dominating. The weakly convex domination number \gamma_wcon(G) of a graph G equals the minimum cardinality of a weakly convex dominating set in G. The weakly convex domination subdivision number sd_wcon (G) is the minimum...
-
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...
-
Graph Representation Integrating Signals for Emotion Recognition and Analysis
PublikacjaData reusability is an important feature of current research, just in every field of science. Modern research in Affective Computing, often rely on datasets containing experiments-originated data such as biosignals, video clips, or images. Moreover, conducting experiments with a vast number of participants to build datasets for Affective Computing research is time-consuming and expensive. Therefore, it is extremely important to...
-
Nordhaus-Gaddum results for the weakly convex domination number of a graph
PublikacjaArtykuł dotyczy ograniczenia z góry i z dołu (ze względu na ilość wierzchołków) sumy i iloczynu liczb dominowania wypukłego grafu i jego dopełnienia.
-
Harmonions Coloring of Graphs.
PublikacjaProblem kolorowania grafów jest motywowany radionawigacją lotniczą, kompresją obrazów i in. W rozdziale podano podstawowe fakty dotyczące tego modelu kolorowania, a wsród nich dolne i górne oszacowania na liczbę harmoniczną i algorytm o złożoności 0 (mm3) dający bardzo dobre pokolorowania przybliżone.
-
Classical coloring of graphs.
PublikacjaRozdział obejmuje klasyczne kolorowanie krawędzi i wierzołków w grafach prostych. Oprócz podstawowych definicji podane zostały najczęściej stosowane metody przybliżone oraz ich właściwości. Dodatkowo rozdział zawiera przegląd znanych benczmarków dla podanych metod w kontekście klasycznego modelu kolorowania.
-
Sum Coloring of Graphs.
PublikacjaRozdział jest poświęcony sumacyjnemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Rank Coloring of Graphs.
PublikacjaRozdział jest poświęcony uporządkowanemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
T-coloring of graphs.
PublikacjaNiniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana została jego definicja i podstawowe własności, zastosowania oraz złożoność obliczeniowa problemów rozważanych w ramach tej dziedziny.
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Publikacja -
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublikacjaW artykule rozważamy listowo-kosztowe kolorowanie wierzchołków i krawędzi grafu w modelu wierzchołkowym, krawędziowym, totalnym i pseudototalnym. Stosujemy programowanie dynamiczne w celu otrzymania algorytmów wielomianowych dla drzew. Następnie uogólniamy to podejście na dowolne grafy z ograniczonymi liczbami cyklomatycznymi i na ich multikolorowania.
-
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/.
-
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines
PublikacjaIn 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
Publikacjagenetic 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
PublikacjaIn 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:...
-
Interval Edge-Coloring of Graphs
Publikacja -
On the complexity of distributed greedy coloring
PublikacjaW pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.
-
On efficient coloring of chordless graphs
PublikacjaArtykuł omawia zagadnienie optymalnego, wielomianowego rozpoznawania i kolorowania grafów bezcięciwowych. Zawiera dowód tego, że takie grafy są zawsze 4-kolorowalne oraz opis wielomianowego algorytmu, który koloruje je minimalną możliwą liczbą kolorów.
-
Path Coloring and Routing in Graphs.
PublikacjaW rozdziale omówione zostały problemy kolorowania ścieżek i routingu w grafach. Podano podstawowe definicje związane z tymi problemami, znane wyniki wraz z dyskusją złożoności obliczeniowej dla grafów ogólnych i dla kilku podstawowych klas grafów oraz zastosowania.
-
Interval edge-coloring of graphs.
PublikacjaRozdział poświęcony prezentacji modelu zwartego kolorowania krawędziowego grafów i jego znanych własności. Szczególny nacisk położono na opis klas grafów dających się pokolorować zwarcie w czasie wielomianowym. Omówiono także stratność jako miarę niepodatności grafu na kolorowanie zwarte.
-
Forwarding and optical indices of a graph
PublikacjaW 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.
-
On a Recurrence Arising in Graph Compression
PublikacjaIn 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
PublikacjaNr 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...
-
Graph models of clos networks
Publikacja...
-
Neural Graph Collaborative Filtering: Analysis of Possibilities on Diverse Datasets
PublikacjaThis 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ż.
OsobyUkoń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...
-
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.
-
Emotion Recognition from Physiological Channels Using Graph Neural Network
PublikacjaIn 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...
-
On the total restrained domination number of a graph
PublikacjaW pracy przedstawione są ograniczenia i własności liczby dominowania podwójnie totalnego.
-
The outer-connected domination number of a graph
PublikacjaW pracy została zdefiniowana liczba dominowania zewnętrznie spójnego i przedstawiono jej podstawowe własności.
-
The task graph assignment for KASKADA platform
PublikacjaArtykuł 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
PublikacjaW pracy została zdefiniowana liczba dominowania podwójnie spójnego i przedstawiono jej podstawowe własności.
-
Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph
PublikacjaA 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...
-
Sum Coloring of Bipartite Graphs with Bounded Degree
Publikacja -
Sum coloring of bipartite graphs with bounded degree.
PublikacjaArtykuł poświęcony jest złożoności obliczeniowej zagadnienia sumacyjnego kolorowania grafów dwudzielnych o ograniczonym stopniu. Zawiera dowód tego, że sumacyjne kolorowanie grafów dwudzielnych stopnia mniejszego równego 5 jest NP-zupełne oraz opis wielomianowego algorytmu, który optymalnie sumacyjnie koloruje grafy dwudzielne podkubiczne.
-
Self-stabilizing algorithm for edge-coloring of graphs
PublikacjaReferat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu wraz z dowodem poprawności oraz oszacowaniem jego czasu działania.
-
The smallest hard-to-color graph for algorithm DSATUR
Publikacja -
The smallest hard-to-color graph for the SL algorithm
Publikacja -
Graph Approach to the Computation of the Homology of Continuous Maps
Publikacja -
Graph decomposition for improving memoryless periodic exploration
PublikacjaW 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.