Wyniki wyszukiwania - BazTech

1

Zastosowanie struktury zbiorów rozłącznych w algorytmie Kruskala

Kucharewicz Bartosz, Kucharczyk Marta, Wieczorek Bożena

MINUT Matematyka i Informatyka na Uczelniach Technicznych

|

2025

|

Nr 7

192-205

PL

We współczesnym świecie wiele problemów związanych z optymalizacja połączeń w sieciach komputerowych, energetycznych czy drogowych znajduje matematyczne rozwiązanie w teorii grafów. Jednym z najistotniejszych zagadnień w tej dziedzinie jest wyznaczanie minimalnego drzewa rozpinającego (ang. Minimum Spannig Tree).W niniejszym artykule zaprezentowane zostaną dwa sposoby implementacji algorytmu Kruskala, różniące sie podejściem do wykrywania cykli - metoda wykorzystująca strukturę zbiorów rozłącznych (ang. Disjoint Set Union lub Union-Find data structure) oraz rozwiązanie wykorzystujące własność spójnych składowych.

2

Modernisation of container ship fleets: state of play and consequences for the Baltic Sea

Kerbiriou R.

TransNav : International Journal on Marine Navigation and Safety of Sea Transportation

|

2024

|

Vol. 18 No. 1

211--217

EN

In order to adapt to structural changes in world trade, container ship owners have developed their transport services. Thus, the unit transport capacity of container ships has been multiplied by 3 in the space of 20 years. The maritime transport of containers has developed very speedily and there have been changes in the strategies of shipping companies. These giants of the seas, put into service on the maritime trades linking the world's main production and consumption markets, have led to the repositioning of ships on secondary maritime spaces. This is known as cascading. The objective of this paper is to study the impacts on the ports and the maritime network of the Baltic Sea. For this purpose, we will carry out an analysis of the evolution of container ship calls from 2012 to 2020 (number of calls, capacity offered in calls, ...) followed by a graph analysis to study the evolution of the maritime network.

3

An approach to the analysis of critical elements of transport and logistics networks using graph theory

Strzelczyk Adriana, Guze Sambor

TransNav : International Journal on Marine Navigation and Safety of Sea Transportation

|

2024

|

Vol. 18 No. 3

535--544

EN

The article's primary purpose is to develop methods for determining critical nodes, arcs, and routes of transport and logistics networks. One of the proposed algorithms resolves a problem in finding the critical elements of the transport network. The second gives solutions to make alternative paths based on this criticality of the network. These tools should be helpful for transport planners, especially for dangerous, oversized, and important goods. The basis of the developed method is the domination in graphs. The proposed analysis methodology is verified on the existing infrastructure in northeastern Poland.

4

Assumptions for the mathematical model investigating the effect of railway line route parameters on the average speed of railway vehicles

Krzykawski Martin, Burdzik Rafał, Gołębiowski Piotr

Prace Naukowe Politechniki Warszawskiej. Transport

|

2024

|

z. 139

5--18

EN

Rail transport is the most efficient alternative to road transport. The popularity of this branch is constantly growing. As a consequence, it is noticed that key terminals, railway routes and HUB stations are constantly being overloaded, resulting in a reduction in the available capacity. This necessitates the passage of higher priority trains (mainly passenger trains), which requires the introduction of additional stops for freight trains and consequently reduces commercial speeds. A railway line is characterized, m.in, by parameters such as: electrification, maximum speed, railway line class, track width, etc. Each of these parameters can have an impact on the average speed of rail vehicles in rail transport. An additional factor determining speed is the capacity of railway lines. Due to the lower capacity and the consequent low average commercial speed, alternative routes for trains are being sought. The aim of the article is to analyze the assumptions for the mathematical model of the influence of technical parameters of routes and capacity of railway lines on the average speed of rail vehicles. In order to achieve this goal, the article is divided into five sections. The first section is an introduction to the article. The second section describes theoretical issues related to modelling in transport. The third section describes the issues of mathematical modeling using graph theory. The practical application of graph theory on the selected example is described in the fourth section. A summary of the article and preliminary research is presented in the last section.

PL

Transport kolejowy stanowi najefektywniejszą alternatywę dla transportu samochodowego. Popularność tej gałęzi ciągle rośnie. W konsekwencji zauważa się, że kluczowe terminale, szlaki kolejowe i stacje HUBowe są ciągle dociążane, w efekcie czego zmniejsza się dostępna na nich przepustowość. Wymusza to konieczność przepuszczania pociągów o wyższym priorytecie (głównie pociągów pasażerskich), co wymaga wprowadzenia dodatkowych postojów dla pociągów towarowych i w konsekwencji powoduje zmniejszanie prędkości handlowej. Linia kolejowa charakteryzowana jest m.in. przez takie parametry jak: elektryfikacja, prędkość maksymalna, klasa linii kolejowej, szerokość toru itd. Każdy z tych parametrów może mieć wpływ na średnią prędkość pojazdów szynowych w transporcie kolejowym. Dodatkowym czynnikiem determinującym prędkość jest przepustowość linii kolejowych. W związku z mniejszą przepustowością oraz w konsekwencji niską średnią prędkością handlową poszukuje się alternatywnych tras dla pociągów. Celem badań przedstawionych w niniejszym artykule jest analiza założeń do modelu matematycznego definiującego wpływ parametrów trasy linii kolejowej na średnią prędkość pojazdów szynowych w transporcie kolejowym. Aby zrealizować tak postawiony cel artykuł podzielono na pięć sekcji. Sekcja pierwsza stanowi wprowadzenie do artykułu. W sekcji drugiej opisano zagadnienia teoretyczne w odniesieniu do problematyki modelowania w transporcie. Sekcja trzecia opisuje zagadnienia modelowania matematycznego z wykorzystaniem teorii grafów. Praktyczne zastosowanie teorii grafów na wybranym przykładzie opisano w sekcji czwartej. Podsumowanie artykułu i wstępnych badań przedstawiono w ostatniej sekcji.

5

Enhancing multi-class prediction of skin lesions with feature importance assessment

Paulauskaite-Taraseviciene Agne, Sutiene Kristina, Dimsa Nojus, Valiukeviciene Skaidra

International Journal of Applied Mathematics and Computer Science

|

2024

|

Vol. 34, no. 4

617--629

EN

Numerous image processing techniques have been developed for the identification of various types of skin lesions. In real-world scenarios, the specific lesion type is often unknown in advance, leading to a multi-class prediction challenge. The available evidence underscores the importance of employing a comprehensive array of diverse features and subsequently identifying the most important ones as a crucial step in visual diagnostics. For this purpose, we addressed both binary and five-class classification tasks using a small dataset, with skin lesions prevalent in Lithuania. The model was trained using a rich set of 662 features, encompassing both conventional image features and graph-based ones, which were obtained from the superpixel graph generated using Delaunay triangulation. We explored the influence of feature importance determined by SHAP values, resulting in a weighted F1-score of 92.48% for the two-class classification and 71.21% for the five-class prediction.

6

On Iiro Honkala's contributions to identifying codes

Hudry Olivier, Junnila Ville, Lobstein Antoine

Fundamenta Informaticae

|

2024

|

Vol. 191, nr 3-4

165--196

EN

A set C of vertices in a graph G = (V, E) is an identifying code if it is dominating and any two vertices of V are dominated by distinct sets of codewords. This paper presents a survey of Iiro Honkala’s contributions to the study of identifying codes with respect to several aspects: complexity of computing an identifying code, combinatorics in binary Hamming spaces, infinite grids, relationships between identifying codes and usual parameters in graphs, structural properties of graphs admitting identifying codes, and number of optimal identifying codes.

7

Surgical phase classification and operative skill assessment through spatial context aware CNNs and time-invariant feature extracting autoencoders

Pradeep Chakka Sai, Sinha Neelam

Biocybernetics and Biomedical Engineering

|

2023

|

Vol. 43, no. 4

700--724

EN

Automated surgical video analysis promises improved healthcare. We propose novel spatial context aware combined loss function for end-to-end Encoder-Decoder training for Surgical Phase Classification (SPC) on laparoscopic cholecystectomy (LC) videos. Proposed loss function leverages on fine-grained class activation maps obtained from fused multi-layer Layer-CAM for supervised learning of SPC, obtaining improved Layer-CAM explanations. Post classification, we introduce graph theory to incorporate known hierarchies of surgical phases. We report peak SPC accuracy of 96.16%, precision of 94.08% and recall of 90.02% on public dataset Cholec80, with 7 phases. Our proposed method utilizes just 73.5% of parameters as against existing state-of-the-art methodology, achieving improvement of 0.5% in accuracy, 1.76% in precision with comparable recall, with an order less standard deviation. We also propose DNN based surgical skill assessment methodology. This approach utilizes surgical phase prediction scores from the final fully-connected layer of spatial-context aware classifier to form multi-channel temporal signal of surgical phases. Time-invariant representation is obtained from this temporal signal through time- and frequency-domain analyses. Autoencoder based time-invariant features are utilized for reconstruction and identification of prominent peaks in dissimilarity curves. We devise a surgical skill measure (SSM) based on spatial-context aware temporal-prominence-of-peaks curve. SSM values are expected to be high when executed skillfully, aligning with expert assessed GOALS metric. We illustrate this trend on Cholec80 and m2cai16-tool datasets, in comparison with GOALS metric. Concurrence in the trend of SSM with respect to GOALS metric is obtained on these test videos, making it a promising step towards automated surgical skill assessment.

8

Tendencies of Chinese subways’ spatial growth in 2000-2020

Panov Roman

Prace Komisji Geografii Komunikacji PTG

|

2022

|

nr 25(2)

42--51

EN

One of the main transportation problems of biggest modern cities is the excessively high load on ground transport, which is why the development of subway networks is of particular importance. This article analyzes the development of the spatial structure of subway networks in China. Currently China shows an intensive growth of existing networks and massive openings of new networks, which makes it the most suitable object for studying the evolution of subway networks. The methodology developed by K. Kansky and S. A. Tarkhov was used as the theoretical basis of this study. The study was conducted by analyzing the dynamics of the main quantitative and topomorphological indicators of subway networks during their passage through the stages of spatial evolution. The following indicators were used: the number of subways, the total length of the network, the number of cycles in the network, the number of topological layers and the number of cycles in each of them, the number of branching tiers, the area of topological layers and their share in the cyclic core of the network, the distribution of the length between the elements of the network structure, average cycle size, topological limit, cyclization index and circuity index. We identified the patterns for passing the stages of evolutionary development by the networks of Chinese subways; also, we found common features that define the “Chinese” type of subway, we identified a new subtype of networks.

9

A note on possible density and diameter of countere xamples to the Seymour’s second neighborhood conjecture

Zelenskiy Oleksiy, Darmosiuk Valentyna, Nalivayko Illia

Opuscula Mathematica

|

2021

|

Vol. 41, no. 4

601--605

EN

Seymour’s second neighborhood conjecture states that every simple digraph without loops or 2-cycles contains a vertex whose second neighborhood is at least as large as its first. In this paper we show, that from falsity of Seymour’s second neighborhood conjecture it follows that there exist strongly-connected counterexamples with both low and high density (dense and sparse graph). Moreover, we show that if there is a counterexample to conjecture, then it is possible to construct counterexample with any diameter k ≥ 3

10

Metoda upraszczania struktur sieci gazowych

Osiadacz Andrzej J., Strzałkowski Krzysztof, Kotyński Łukasz

Gaz, Woda i Technika Sanitarna

|

2021

|

Nr 10

2--6

PL

W artykule omówiono metodę upraszczania struktury sieci gazowej. Metoda upraszcza strukturę eliminując część elementów sieci zachowując przy tym parametry hydrauliczne sieci rzeczywistej. Weryfikacji metody dokonano upraszczając struktury wielu sieci rzeczywistych.

EN

The paper presents a method for the reduction of gas networks structure. The method reduces a network structure equivalent to the original one, but which contains fewer components. The method was validated by simplifying many gas networks.

11

An ant algorithm for the maximum number of 3-cliques in 3-partite graphs

Schiff Krzysztof

Control and Cybernetics

|

2021

|

Vol. 50, No. 2

347--358

EN

The problem of finding the maximum number of d- vertices cliques (d = 3) in d-partite graph (d = 3) when graph density q is lower than 1 is an important problem in combinatorial optimization and it is one of many NP-complete problems. For this problem a meta-heuristic algorithm has been developed, namely an ant colony optimization algorithm. In this paper a new development of this ant algorithm and experimental results are presented. The problem of finding the maximum number of 3-vertices cliques can be encountered in computer image analysis, computer vision applications, automation and robotic vision systems. The optimal solution of this problem boils down to finding a set of 3-vertices cliques in a 3-partite graph and this set should have cardinality as high as possible. The elaborated ant colony algorithm can be easily modified for d-dimensional problems, that is for finding the maximum number of d-vertices cliques in a d-partite graph.

12

Multi-sourced power system restoration strategy based on modified Prim’s algorithm

Łukaszewski Artur, Nogal Łukasz

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2021

|

Vol. 69, nr 5

art. no. e137942

EN

Self-healing grids are one of the most developing concepts applied in electrical engineering. Each restoration strategy requires advanced algorithms responsible for the creation of local power systems. Multi-agent automation solutions dedicated for smart grids are mostly based on Prim’s algorithm. Graph theory in that field also leaves many problems unsolved. This paper is focused on a variation of Prim’s algorithm utility for a multi-sourced power system topology. The logic described in the paper is a novel concept combined with a proposal of a multi-parametrized weight calculation formula representing transmission features of energy delivered to loads present in a considered grid. The weight is expressed as the combination of three elements: real power, reactive power, and real power losses. The proposal of a novel algorithm was verified in a simulation model of a power system. The new restoration logic was compared with the proposal of the strategy presented in other recently published articles. The novel concept of restoration strategy dedicated to multi-sourced power systems was verified positively by simulations. The proposed solution proved its usefulness and applicability.

13

Rotation Invariance in Graph Convolutional Networks

Mac Nguyen Anh, Nguyen Hung Son

Annals of Computer Science and Information Systems

|

2021

|

Vol. 25

81--90

EN

Convolution filters in deep convolutional networks display rotation variant behavior. While learned invariant behavior can be partially achieved, this paper shows that current methods of utilizing rotation variant features can be improved by proposing a grid-based graph convolutional network. We demonstrate that Grid-GCN heavily outperforms existing models on rotated images, and through a set of ablation studies, we show how the performance of Grid-GCN implies that there exist more performant methods to utilize fundamentally rotation variant features and we conclude that the inherit nature of spectral graph convolutions is able to learn invariant behavior.

14

Discovering Communities in Networks: A Linear Programming Approach Using Max-Min Modularity

Ferdowsi Arman, Khanteymoori Alireza

Annals of Computer Science and Information Systems

|

2021

|

Vol. 25

329–-335

EN

Community detection is a fundamental challenge in network science and graph theory that aims to reveal nodes' structures. ‎While most methods consider Modularity as a community quality measure‎, ‎Max-Min Modularity improves the accuracy of the measure by penalizing the Modularity quantity when unrelated nodes are in the same community‎. ‎In this paper‎, ‎we propose a community detection approach based on linear programming using Max-Min Modularity‎. ‎The experimental results show that our algorithm has a better performance than the previously known algorithms on some well-known instances‎.

15

Combinatorial Etude

Stoenchev Miroslav, Todorov Venelin

Annals of Computer Science and Information Systems

|

2021

|

Vol. 25

231--234

EN

The purpose of this article is to consider a special class of combinatorial problems, the so called Prouhet-Tarry Escot problem, solution of which is realized by constructing finite sequences of ±1. For example, for fixed p∈N, is well known the existence of np∈N with the property: any set of np consecutive integers can be divided into 2 sets, with equal sums of its p[th] powers. The considered property remains valid also for sets of finite arithmetic progressions of complex numbers.

16

An Efficient Connected Swarm Deployment via Deep Learning

Danilchenko Kiril, Segal Michael

Annals of Computer Science and Information Systems

|

2021

|

Vol. 25

1--7

EN

In this paper, an unmanned aerial vehicles (UAVs) deployment framework based on machine learning is studied. It aims to maximize the sum of the weights of the ground users covered by UAVs while UAVs forming a connected communication graph. We focus on the case where the number of UAVs is not necessarily enough to cover all ground users. We develop an UAV Deployment Deep Neural network (mod) as a UAV's deployment deep network method. Simulation results demonstrate that mod can serve as a computationally inexpensive replacement for traditionally expensive optimization algorithms in real-time tasks and outperform the state-of-the-art traditional algorithms.

17

An Efficient Approach Towards the Generation and Analysis of Interoperable Clinical Data in a Knowledge Graph

Dörpinghaus Jens, Weil Vera, Schaaf Sebastian, Hübenthal Tobias

Annals of Computer Science and Information Systems

|

2021

|

Vol. 25

59--68

EN

Knowledge graphs have been shown to play an important role in recent knowledge mining and discovery, for example in the field of life sciences or bioinformatics. Contextual information is widely used for NLP and knowledge discovery in life sciences since it highly influences the exact meaning of natural language and also queries for data. The contributions of this paper are (1) an efficient approach towards interoperable data, (2) a runtime analysis of 14 real world use cases represented by graph queries and (3) a unique view on clinical data and its application combining methods of algorithmic optimisation, graph theory and data science.

18

The reactive power and voltage control management strategy based on virtual reactance cloud control

Zhang Wei Min, Zhang Yan Xia

Archives of Electrical Engineering

|

2020

|

Vol. 69, nr 4

921--936

EN

The paper aims at the higher reactive power management complexity caused by the access of distributed power, and the problem such as large data exchange capacity, low accuracy of reactive power distribution, a slow convergence rate, and so on, may appear when the controlled objects are large. This paper proposes a reactive power and voltage control management strategy based on virtual reactance cloud control. The coupling between active power and reactive power in the system is effectively eliminated through the virtual reactance. At the same time, huge amounts of data are treated to parallel processing by using the cloud computing model parallel distributed processing, realize the uncertainty transformation between qualitative concept and quantitative value. The power distribution matrix is formed according to graph theory, and the accurate allocation of reactive power is realized by applying the cloud control model. Finally, the validity and rationality of this method are verified by testing a practical node system through simulation.

19

Optimization of Retrieval Algorithms on Large Scale Knowledge Graphs

Dörpinghaus Jens, Stefan Andreas

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

227--236

EN

Knowledge graphs have been shown to play an important role in recent knowledge mining and discovery, for example in the field of life sciences or bioinformatics. Although a lot of research has been done on the field of query optimization, query transformation and of course in storing and retrieving large scale knowledge graphs the field of algorithmic optimization is still a major challenge and a vital factor in using graph databases. Few researchers have addressed the problem of optimizing algorithms on large scale labeled property graphs. Here, we present two optimization approaches and compare them with a naive approach of directly querying the graph database. The aim of our work is to determine limiting factors of graph databases like Neo4j and we describe a novel solution to tackle these challenges. For this, we suggest a classification schema to differ between the complexity of a problem on a graph database. We evaluate our optimization approaches on a test system containing a knowledge graph derived biomedical publication data enriched with text mining data. This dense graph has more than 71M nodes and 850M relationships. The results are very encouraging and -- depending on the problem -- we were able to show a speedup of a factor between 44 and 3839.

20

On Finding the Optimal Tree of a Complete Weighted Graph

Hosseini Seyed Soheil, Wormald Nick, Tian Tianhai

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

271--275

EN

We want to find a tree where the path length between any two vertices on this tree is as close as possible to their corresponding distance in the complete weighted graph of vertices upon which the tree is built. We use the residual sum of squares as the optimality criterion to formulate this problem, and use the Cholesky decomposition to solve the system of linear equations to optimise weights of a given tree. We also use two metaheuristics, namely Simulated Annealing (SA) and Iterated Local Search (ILS) to optimise the tree structure. Our results suggest that SA and ILS both perform well at finding the optimal tree structure when the dispersion of distances in the complete graph is large. However, when the dispersion of distances is small, only ILS has a solid performance.