Filtry
wszystkich: 909
wybranych: 729
-
Katalog
Filtry wybranego katalogu
Wyniki wyszukiwania dla: GRAPH
-
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.
-
Efficient parallel query processing by graph ranking
PublikacjaW 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.
-
Relations between the domination parameters and the chromatic index of a graph
PublikacjaIn 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.
-
Constructing a map of an anonymous graph: applications of universal sequences
PublikacjaWe 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...
-
On Tradeoffs Between Width- and Fill-like Graph Parameters
PublikacjaIn 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,...
-
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...
-
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...
-
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...
-
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...
-
Greedy algorithms for backbone graph coloring in KOALA library
Publikacja -
On the complexity of distributed graph coloring with local minimality constraints
PublikacjaArtykuł 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.
-
Nordhaus-Gaddum results for the convex domination number of a graph
PublikacjaPraca dotyczy nierówności typu Nordhausa-Gadduma dla dominowania wypukłego.
-
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...
-
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.
-
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...
-
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...
-
Neural Graph Collaborative Filtering: Analysis of Possibilities on Diverse Datasets
Publikacja -
Tighter bounds on the size of a maximum P3-matching in a cubic graph
PublikacjaW 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 mechatronic systems. A bond graph approach
PublikacjaW 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.
-
Towards explainable motion prediction using heterogeneous graph representations
Publikacja -
Modelling of energy flow in electrical machines. A bond graph approach
PublikacjaPrzedstawiono 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.
-
Self-stabilizing algorithms for graph coloring with improved performance guarantees
PublikacjaW 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.
-
Linear game non-contextuality and Bell inequalities—a graph-theoretic approach
PublikacjaWe study the classical and quantum values of a class of one-and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR(XOR-d) games we study are a subclass of the well-known linear games. We introduce a 'constraint graph' associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the...
-
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/.
-
Computer experiments with a parallel clonal selection algorithm for the graph coloring problem
PublikacjaArtificial 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: 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:...
-
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...
-
Network Graph Transformation Providing Fast Calculation of Paths for Resilient Routing
PublikacjaProtection of transmission against failures can be appropriately dealt with by alternative paths. However, common schemes (e.g., Bhandaris scheme) are characterized by a remarkable delay while determining the transmission paths. This in turn may have a serious impact on serving dynamic demands (characterized by relatively short duration time). As a remedy to this problem, we introduce an approach to pre-compute the sets of disjoint...
-
A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints
PublikacjaWe address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem...
-
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...
-
Application of Graph Theory Algorithms in Non-disjoint Functional Decomposition of Specific Boolean Functions
Publikacja -
CAUSALITY IN MODELS OF THERMAL PROCESSES IN SHIP ENGINE ROOMS WITH THE USE OF BOND GRAPH (BG) METHOD
PublikacjaWith 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...
-
Graph Neural Networks and Structural Information on Ionic Liquids: A Cheminformatics Study on Molecular Physicochemical Property Prediction
PublikacjaIonic 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...
-
Non-disjoint Decomposition Using r-admissibility and Graph Coloring and Its Application in Index Generation Functions Minimization
Publikacja -
Model silnika spalinowego w formie grafów wiązań (GW).A model of the IC engine in the form of the bond graph (BG).
PublikacjaPrzedstawiono uzasadnienie użycia metody grafów wiązań do do modelowania silnika spalinowego jako źródła energii w systemach energetycznych składających się z elementów o różnej naturze fizycznej, na przykład w pojazdach hybrydowych. Przedstawiono propozycję formalizacji charakterystyki silników spalinowych wynikającą z przyjętej metody modelowania. Analityczną formę charakterystyki przedstawiono jako wielowymiarową funkcję wektorową....
-
Switched-capacitor DC-DC converters in arbitrary switching mode - topologically derived resistive models based on incremental graph approach.
PublikacjaIn the preceding paper we reviewed some of modeling approaches aimed at systematic formulation and solution of switched capacitor DC-DC converters. In our review, special attention was paid to computationally efficient and mathematically elegant methods. In so doing we had tried to demonstrate the virtues of unified Incremental Graph (IG) approach. Incremental Graph is, in concept, a tool originally created for analysis and synthesis...
-
Kolorowanie grafów z ograniczeniami na liczbę wierzchołków w określonym kolorze = Graph coloring model with restrictions on cardinalities of vertexes in particular color
PublikacjaW artykule rozważamy problem takiego kolorowania grafów, w którym klasy kolorów mają ograniczoną z góry moc. Zagadnie to znajduje ciekawe zastosowania praktyczne i jest naturalnym uogólnieniem problemu kolorowania grafów. W artykule ustalamy złożoność obliczeniową dla grafów pełnych $r$-dzielnych i dla kilku innych prostych klas grafów oraz dla problemu dwukolorowania.
-
Comparison of hydrogen bonds and diverse weak interactions of the nitro group in 2-methyl-4-nitroanilinium nitrate, bisulfate and two hexafluoridosilicates: elementary graph-set approach
PublikacjaCrystal structures of (H2m4na)NO3 (1), (H2m4na)HSO4 (2), (H2m4na)2SiF6 (3) and (H2m4na)2SiF6*2H2O (4), where 2m4na = 2-methyl-4-nitroaniline, are presented. Two layers of interactions occur in the structures, N—H...O/F hydrogen bonds and interactions with the nitro group. Although diverse, hydrogen-bonding patterns are compared with each other by means of interrelations among elementary graph-set descriptors and descriptors of hydrogen-bonding...
-
Bond graph modeling of the new generation engine cooling systems = Zastosowanie metody grafów wiązań do modelowania nowej generacji układów chłodzenia silników spalinowych
PublikacjaW referacie szczegółowo opisano modele wymiany ciepła i przepływów w układzie chłodzenia. Metoda grafów wiązań okazała się szczególnie użyteczną dla modelowania skomplikowanych systemów energetycznych o różnych postaciach energii. Jako przykładu użyto obiegu chłodzenia silnika badawczego na hamowni silnikowej.
-
Graphitic carbon nitride/graphene oxide/reduced graphene oxide nanocomposites for photoluminescence and photocatalysis
Publikacja -
Parity vertex colouring of graphs
PublikacjaA 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-line P-coloring of graphs
PublikacjaFor 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...
-
Some variations of perfect graphs
PublikacjaWe 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...
-
Equitable coloring of corona multiproducts of graphs
PublikacjaWe give some results regarding the equitable chromatic number for l-corona product of two graphs: G and H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G.
-
Interval incidence coloring of subcubic graphs
PublikacjaIn this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is N P-complete, and they asked if χii(G) ≤ 2∆(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with ∆(G) = 3.
-
Domination subdivision and domination multisubdivision numbers of graphs
PublikacjaThe domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T)<=3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number...
-
Total domination in versus paired-domination in regular graphs
PublikacjaA subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the...
-
Block graphs with large paired domination multisubdivision number
PublikacjaThe paired domination multisubdivision number of a nonempty graph G, denoted by msdpr(G), is the smallest positive integer k such that there exists an edge which must be subdivided k times to increase the paired domination number of G. It is known that msdpr(G) ≤ 4 for all graphs G. We characterize block graphs with msdpr(G) = 4.
-
Optimal backbone coloring of split graphs with matching backbones
PublikacjaFor a graph G with a given subgraph H, the backbone coloring is defined as the mapping c: V(G) -> N+ such that |c(u)-c(v)| >= 2 for each edge uv \in E(H) and |c(u)-c(v)| >= 1 for each edge uv \in E(G). The backbone chromatic number BBC(G;H) is the smallest integer k such that there exists a backbone coloring with max c(V(G)) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
-
Graphs with equal domination and 2-distance domination numbers
PublikacjaW publikacji scharakteryzowane są wszystkie te drzewa i grafy jednocykliczne, w których liczba dominowania oraz liczba 2-dominowania na odległość są sobie równe.