Filters
total: 661
filtered: 534
-
Catalog
Chosen catalog filters
Search results for: EVOLAP GRAPH
-
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.
-
Multi-agent graph searching and exploration algorithms
PublicationA 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...
-
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.
-
Connection graphs
Publication -
How Do Intermolecular Interactions Evolve at the Nematic to Twist–Bent Phase Transition?
Publication -
Constructing a map of an anonymous graph: applications of universal sequences
PublicationWe study the problem of mapping an unknown environmentrepresented as an unlabelled undirected graph. A robot (or automaton)starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria...
-
Greedy algorithms for backbone graph coloring in KOALA library
Publication -
Nordhaus-Gaddum results for the convex domination number of a graph
PublicationPraca dotyczy nierówności typu Nordhausa-Gadduma dla dominowania wypukłego.
-
On the complexity of distributed graph coloring with local minimality constraints
PublicationArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.
-
Relations between the domination parameters and the chromatic index of a graph
PublicationIn 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.
-
Pawlak's flow graph extensions for video surveillance systems
PublicationThe 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...
-
Characterizing the Scalability of Graph Convolutional Networks on Intel® PIUMA
PublicationLarge-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...
-
On Tradeoffs Between Width- and Fill-like Graph Parameters
PublicationIn this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the path width pw(G) and the profile p(G) of the input graph G. We prove that for an arbitrary graph G and an integer t ∈ {1,...
-
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...
-
Graph Representation Integrating Signals for Emotion Recognition and Analysis
PublicationData 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...
-
On the deficiency of bipartite graphs
Publication -
Named Property Graphs
Publication -
Serialization for Property Graphs
Publication -
Dynamic coloring of graphs
PublicationDynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In...
-
2-bondage in graphs
PublicationA 2-dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. The 2-bondage number of G, denoted by b_2(G), is the minimum cardinality among all sets of edges E' subseteq E such that gamma_2(G-E') > gamma_2(G). If for every E' subseteq E we have...
-
Double bondage in graphs
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G, denoted by gamma_d(G), is the minimum cardinality of a double dominating set of G. The double bondage number of G, denoted by b_d(G), is the minimum cardinality among all sets...
-
Rank Coloring of Graphs.
PublicationRozdział jest poświęcony uporządkowanemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Circular colorings of graphs.
PublicationRozdział poświęcony jest cyrkularnemu modelowi kolorowania krawędzi. Rozważana jest zarówno wersja wierzchołkowa i krawędziowa. Szczególny nacisk położono na złożoność obliczeniową i zastosowania dla omawianych modeli kolorowania.
-
Harmonions Coloring of Graphs.
PublicationProblem 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.
-
T-coloring of graphs.
PublicationNiniejszy 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.
-
Classical coloring of graphs.
PublicationRozdział 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.
PublicationRozdział jest poświęcony sumacyjnemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Common Independence in Graphs
PublicationAbstract: The cardinality of a largest independent set of G, denoted by α(G), is called the independence number of G. The independent domination number i(G) of a graph G is the cardinality of a smallest independent dominating set of G. We introduce the concept of the common independence number of a graph G, denoted by αc(G), as the greatest integer r such that every vertex of G belongs to some independent subset X of VG with |X|...
-
Strategic balance in graphs
PublicationFor a given graph G, a nonempty subset S contained in V ( G ) is an alliance iff for each vertex v ∈ S there are at least as many vertices from the closed neighbourhood of v in S as in V ( G ) − S. An alliance is global if it is also a dominating set of G. The alliance partition number of G was defined in Hedetniemi et al. (2004) to be the maximum number of sets in a partition of V ( G ) such that each set is an alliance. Similarly,...
-
Self-stabilizing algorithms for graph coloring with improved performance guarantees
PublicationW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
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...
-
Modelling of energy flow in mechatronic systems. A bond graph approach
PublicationW referacie przedstawiono w sposób jednoliy modelowanie systemów mechatroniki metodą grafów wiązań (GW) w aspekcie symulacji przepływu energii. Omówiono ogólne założenia modelowania w ujęciu GW. Modelowanie przepływu energii rozważano na przykładzie napędu pojazdu hybrydowego PH-MAK.
-
Neural Graph Collaborative Filtering: Analysis of Possibilities on Diverse Datasets
Publication -
Tighter bounds on the size of a maximum P3-matching in a cubic graph
PublicationW pracy pokazano, że największe P3-skojarzenie dla dowolnego grafu o n>16 wierzchołkach składa się z przynajmniej 117n/152 wierzchołków.
-
Modelling of energy flow in electrical machines. A bond graph approach
PublicationPrzedstawiono w ujęcia grafów wiązań model przepływu energii/mocy w maszynach elektrycznych pracujących w hybrydowych systemach przetwarzania energii. Jako przykład do rozważań przyjęto system napędu trakcyjnego pojazdów hybrydowych.
-
Nordhaus-Gaddum results for the weakly convex domination number of a graph
PublicationArtykuł 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.
-
Towards explainable motion prediction using heterogeneous graph representations
Publication -
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...
-
Modeling the impact of surface currents in a harbor using graph theory
PublicationEnsuring 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...
-
Non-isolating bondage in graphs
PublicationA dominating set of a graph $G = (V,E)$ is a set $D$ of vertices of $G$ such that every vertex of $V(G) \setminus D$ has a neighbor in $D$. The domination number of a graph $G$, denoted by $\gamma(G)$, is the minimum cardinality of a dominating set of $G$. The non-isolating bondage number of $G$, denoted by $b'(G)$, is the minimum cardinality among all sets of edges $E' \subseteq E$ such that $\delta(G-E') \ge 1$ and $\gamma(G-E')...
-
Deterministic Rendezvous in Restricted Graphs
PublicationIn this paper we consider the problem of synchronous rendezvous in which two anonymous mobile entities (robots) A and B are expected to meet at the same time and point in a graph G = (V;E). Most of the work devoted to rendezvous in graphs assumes that robots have access to the same sets of nodes and edges, where the topology of connections may be initially known or unknown. In our work we assume the movement of robots is restricted...
-
Some variations of perfect graphs
PublicationWe consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) =γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k -path vertex cover number and the distance (k−1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k≥2. Moreover, we provide a complete characterisation of (ψ2−γ1)-perfect graphs describing the set of its forbidden induced subgraphs and providing...
-
On-line P-coloring of graphs
PublicationFor a given induced hereditary property P, a P-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property P. We consider the effectiveness of on-line P-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function...
-
Parity vertex colouring of graphs
PublicationA parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let Xp(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for...
-
On efficient coloring of chordless graphs
PublicationArtykuł 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.
-
Three-fast-searchable graphs
PublicationIn the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...
-
On-line ranking of split graphs
PublicationA vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm...
-
Bondage number of grid graphs
PublicationThe bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. Here we study the bondage number of some grid-like graphs. In this sense, we obtain some bounds or exact values of the bondage number of some strong product and direct product of two paths.
-
Interval Edge-Coloring of Graphs
Publication -
Total restrained bondage in graphs
PublicationPodzbiór D zbioru wierzchołków grafu nazywamy zewnętrznie totalnym dominującym w grafie, jeśli każdy wierzchołek spoza D ma sąsiada zarówno w D jak i poza D. Moc najmniejszego zbioru o tej własności nazywamy liczbą dominowania zewnętrznie totalnego. W artykule badamy wpływ usuwania krawędzi na liczbę dominowania zewnętrznie totalnego, czyli liczbę zewnętrznego totalnego zniewolenie w grafach.