Wyniki wyszukiwania - BazTech

1

Increasing Parallelism in Forward-backward Distributed Algorithm for Finding Strongly Connected Components of Directed Graphs

Ryżko Dominik

Journal of Telecommunications and Information Technology

|

2024

|

nr 3

30--35

EN

The paper proposes a modification of the existing distributed forward-backward algorithm for finding strongly connected components in directed graphs. The modification aims at improving the parallelism of the algorithm by increasing the branching factor while dividing the workload. Instead of randomly picking the pivot vertex, a heuristic technique is used which allows more sub-tasks to be generated, on average, for the subsequent step of the algorithm. The work describes suitable algorithm modifications and presents empirical results, proving suitability of the approach in question.

2

The Applications of Graph Algorithms to Modeling of Integrated Urban Water Management System

Łazuka Ewa, Futa Anna, Jastrzębska Magdalena, Łagód Grzegorz, Szeląg Bartosz, Fatone Francesco

Advances in Science and Technology. Research Journal

|

2022

|

Vol. 16, no 5

277--289

EN

The application of methods using graphs to model a variety of engineering issues has been known for several decades, but the application of graph algorithms to model the urban water management issues is a completely new approach. The article reviews the scientific literature on integrated urban water management systems in terms of the use of graph theory algorithms in this topic. Such a review has not been done before and constitutes a completely novel study. Some of the algorithms presented are directly derived from graph theory, while others were developed from other sciences, including environmental engineering or genetics, to solve specific engineering problems. The paper presents a general scheme and a brief description of the most important components of an integrated urban water management system. The necessary concepts of graphs were defined, the origin and the principle of graph algorithms used in modeling water management issues (Loop-By-Loop Cutting Algorithm, Hanging Gardens Algorithm, Tree Growth Algorithm, Dijkstra’s Algorithm, Genetic Algorithm, and Bayesian Networks Algorithm) were described. Their use in modeling the issues in stormwater, sanitary sewage and water distribution system was described. A complete list of scientific literature in this field was provided.

3

A genetic algorithm for the maximum 2-packing set problem

Trejo-Sánchez Joel Antonio, Fajardo-Delgado Daniel, Gutierrez-Garcia J. Octavio

International Journal of Applied Mathematics and Computer Science

|

2020

|

Vol. 30, no. 1

173--184

EN

Given an undirected connected graph G = (V, E), a subset of vertices S is a maximum 2-packing set if the number of edges in the shortest path between any pair of vertices in S is at least 3 and S has the maximum cardinality. In this paper, we present a genetic algorithm for the maximum 2-packing set problem on arbitrary graphs, which is an NP-hard problem. To the best of our knowledge, this work is a pioneering effort to tackle this problem for arbitrary graphs. For comparison, we extended and outperformed a well-known genetic algorithm originally designed for the maximum independent set problem. We also compared our genetic algorithm with a polynomial-time one for the maximum 2-packing set problem on cactus graphs. Empirical results show that our genetic algorithm is capable of finding 2-packing sets with a cardinality relatively close (or equal) to that of the maximum 2-packing sets. Moreover, the cardinality of the 2-packing sets found by our genetic algorithm increases linearly with the number of vertices and with a larger population and a larger number of generations. Furthermore, we provide a theoretical proof demonstrating that our genetic algorithm increases the fitness for each candidate solution when certain conditions are met.

4

Experimental structure of discourse: mapping the discourse formations of Bauhaus ideals

Lam Ka-man, Gorle Jyotsna, Wilde Michael, Saad Patrick

Architecturae et Artibus

|

2020

|

Vol. 12, no. 1

15--28

EN

In the relativistic world of the 21st century, if the Bauhaus would still be upheld as doctrine, we must face the truth: it can hardly be considered a provocation. Rather, we most often find ourselves caught between contradictory wishes to preserve an intact past and to make sense of a resolute avant-gardism. This paper proposes that the Bauhaus, as a discursive knowledge body, be structuralistically analyzed with Foucauldian Discourse Analysis. Our claim is substantiated by: first, that a F oucaultian concept of discourse offers an alternative to the practice of history and theory; second, that the publication of Bauhaus reveals a discursive structure in a F oucaultian sense; third, that discourse-analysis-search-engine can perform the analysis on the Bauhaus corpus, contributing to emergent epistemological positions; fourth, that this revealed structure of discourse could be mapped and re-materialized to invite interferences on today’s territory of Bauhaus Discourse. The research and development process in the accompanying project “Bauhaus Orbits – scenographic apparatus for discourse analysis” (bauhausorbits.de) will be discussed.

5

Innovative Method of the Evaluation of Multicriterial Multicast Routing Algorithms

Stachowiak K., Zwierzykowski P.

Journal of Telecommunications and Information Technology

|

2013

|

nr 1

49-55

EN

Theoretical considerations of the multicast Quality of Service (QoS) routing have been a rapidly developing and dynamic research area for years. Several algorithms derived from different approaches have been proposed, while the pool of valid solutions to the problem is steadily growing. When new solutions are compared with their predecessors, as much information as possible about their characteristics and differences is needed. Both the graph theory and the optimization theory provide robust and objective means of comparing not only algorithms, but also the results they produce. However, any possible extension to the comparison methods is vital and can bring interesting new information that would eventually lead to innovative conclusions. This article presents a method, derived from practice and experience, that simulates the drainage of resources accumulated by consecutive communication allocations. The nature of this comparison is an extension to the classical measurement of the success ratio and this creates a context of the continuous measure of a success rather than a simple binary value. In this article such a method with regard to algorithms optimizing multicast problems for more than two criteria is used for the first time and leads to an interesting conclusion about the influence of the number of the criteria on the result.

6

Solving Markov decision processes by d-graph algorithms

Kátai Z.

Control and Cybernetics

|

2012

|

Vol. 41, no. 3

577-593

EN

Markov decision processes (MDPs) provide a mathematical model for sequential decisionmaking (sMDP/dMDP: stochastic/ deterministic MDP). We introduce the concept of generalized dMDP (g-dMDP) where each action may result in more than one next (parallel or clone) state. The common tools to represent dMDPs are digraphs, but these are inadequate for sMDPs and g-dMDPs. We introduce d-graphs as general tools to represent all the above mentioned processes (stationary versions). We also present a combined d-graph algorithm that implements dynamic programming strategies to find optimal policies for the finite/infinite horizon versions of these Markov processes. (The preliminary version of this paper was presented at the Conference MACRo 2011.)

7

Wykrywanie modyfikacji kształtu brył z wykorzystaniem algorytmów grafowych

Mikoda J.

Metody Informatyki Stosowanej

|

2011

|

nr 2

89-95

EN

This article presents new method for improving efficiency of applications used for fulfilling given shape with tetrahedral elements. The new approach involves searching for areas in which the shape has changed, and regeneration of mesh elements only in those areas. This operation requires using of fast algorithm for comparision of two independent areas. As a result of comparison a set of areas that should be modified is obtained. Description based on graph was used to describe areas shape while searching for modified areas. Using graphs built on the basis of original and modified shape description allows for using graph algorithms. Using algorithms designed for graph searching and dividing subgraphs made it possible to make faster and simplify process of searching for modified areas.

8

Wykorzystanie elementów teorii grafów w systemie analiz kryminalnych

Gałuszka A., Bereska D., Simek K., Skrzypczyk K., Daniec K.

Przegląd Elektrotechniczny

|

2010

|

R. 86, nr 9

278-283

PL

Celem opracowania jest przegląd metod przeszukiwania grafów będących ilustracją graficzną powiązań pomiędzy zdarzeniami, osobami, będącymi przedmiotem dochodzenia, śledztwa. Przyjmuje się, że zdarzenia (osoby), będące przedmiotem śledztwa (dochodzenia), tworzą zbiór wierzchołków grafu, natomiast możliwe powiązania pomiędzy takimi węzłami, wynikające z zebranych w dochodzeniu faktów, tworzą zbiór krawędzi grafu. Dodatkowo przyjmuje się, że siła związku pomiędzy wierzchołkami jest opisana za pomocą liczby, zwanej wagą krawędzi.

EN

Aim of this paper is to review graph methods that can be applied to criminal analysis system. It is assumed that persons (happenings) of the investigation are represented by the vertices of a graph, and possible connections are represented by edges. Additionally it is assumed that the strength of the connection is described by the number, called the weight of the edge.

9

The Embedding Problem for Switching Classes of Graphs

Ehrenfeucht A., Hage J., Harju T., Rozenberg G.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 1

115-134

EN

In the context of graph transformation we look at the operation of switching, which can be viewed as a method for realizing global transformations of (group-labelled) graphs through local transformations of the vertices. In case vertices are given an identity, various relatively efficient algorithms exist for deciding whether a graph can be switched so that it contains some other graph, the query graph, as an induced subgraph. However, when considering graphs up to isomorphism, we immediately run into the graph isomorphism problem for which no efficient solution is known. Surprisingly enough however, in some cases the decision process can be simplified by transforming the query graph into a ``smaller'' graph without changing the answer. The main lesson learned is that the size of the query graph is not the dominating factor, but its cycle rank. Although a number of our results hold specifically for undirected, unlabelled graphs, we propose a more general framework and give many positive and negative results for more general cases, where the graphs are labelled with elements of a (finitely generated abelian) group.

10

Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes

Hage J., Harju T., Welzl E.

Fundamenta Informaticae

|

2003

|

Vol. 58, nr 1

23--37

EN

In the context of graph transformations we look at the operation of switching, which can be viewed as a method for realizing global transformations of graphs through local transformations of the vertices. A switching class is then a set of graphs obtainable from a given start graph by applying the switching operation. Continuing the line of research in Ehrenfeucht, Hage, Harju and Rozenberg we consider the problem of detecting three kinds of graphs in switching classes. For all three we find algorithms running in time polynomial in the number of vertices in the graphs, although switching classes contain exponentially many graphs.

11

Wielomianowy heurystyczny algorytm wyznaczania kliki maksymalnej O(n4)

Schiff K.

Elektrotechnika i Elektronika

|

2000

|

T. 19, z. 1

17--20

PL

W artykule przedstawiono wielomianowy heurystyczny algorytm wyznaczania kliki maksymalnej o złożoności obliczeniowej rzędu O(n4). Algorytm został oparty o opracowaną metodę sukcesywnego wyznaczania, bezpośrednio z macierzy sąsiedztwa wierzchołków najbardziej nadających się do utworzenia kliki o maksymalnym wymiarze.

EN

In this paper heuristic algorithm with poły nominal computational complexity O(n4) for maximal clique problem is presented. This algorithm is based on successive designation of vertex from incidence matrix, which are the most suitable for maximal clique creation.

12

Dynamic flows with supply and demand

Ciurea E.

Control and Cybernetics

|

2000

|

Vol. 29, no 4

895-903

EN

We are given a network G = (N, A, h, c) with node set N, arc set A, time function h, capacity function c, and P the set of periods, s the source and s' the sink of the network G. Associated with s, there is a non-negative real number q(t) called the supply of source s at time t, and with s' - a nonnegative real number q'(t) called the demand of sink s' at time t, t [belongs to] P. The objective is to determine the existence of a dynamic flow in G for p periods, so that the demands at sink s' can be fulfilled from the supplies at the source s. A numerical example is presented.