Wyniki wyszukiwania - BazTech

1

New Algorithm Permitting the Construction of an Effective Spanning Tree

Belkacem Salima Nait, Abbasy Moncef

Foundations of Computing and Decision Sciences

|

2023

|

Vol. 48, No. 3

313--329

EN

In this paper, we have done a rapid and very simple algorithm that resolves the multiple objective combinatorial optimization problem. This, by determining a basic optimal solution, which is a strong spanning tree constructed, according to a well-chosen criterion. Consequently, our algorithm uses notions of Bellman’s algorithm to determine the best path of the network, and Ford Fulkerson’s algorithm to maximise the flow value. The Simplex Network Method that permits to reach the optimality conditions manipulates the two algorithms. In short, the interest of our work is the optimization of many criteria taking into account the strong spanning tree, which represents the central angular stone of the network. To illustrate that, we propose to optimize a bi-objective distribution problem.

2

Understanding the Impact of COVID–19 on Global Financial Network Using Graph Based Algorithm: Minimum Spanning Tree Approach

Hatipoğlu Veysel Fuat

Foundations of Computing and Decision Sciences

|

2021

|

Vol. 46, No. 1

111--123

EN

In this paper effects of COVID–19 pandemic on stock market network are analyzed by an application of operational research with a mathematical approach. For this purpose two minimum spanning trees for each time period namely before and during COVID–19 pandemic are constructed. Dynamic time warping algorithm is used to measure the similarity between each time series of the investigated stock markets. Then, clusters of investigated stock markets are constructed. Numerical values of the topology evaluation for each cluster and time period is computed.

3

On some aspects of graph theory for optimal transport among marine ports

Chládek P., Smetanová D., Krile S.

Zeszyty Naukowe. Transport / Politechnika Śląska

|

2018

|

z. 101

37--45

EN

This paper is devoted to the Travelling Salesman Problem as applied to Czechoslovak ocean shipping companies and their marine ports on the Black Sea. The shortest circular path around these ports is found and discussed. Formulation of the problem accounts for the fact that distances between the individual cities are not the same in both directions. The consequences that arise from this situation are studied. The used algorithms are based on graph theory and standard logistic methods. In addition, the results are compared with the results obtained by using a minimum spanning tree algorithm.

4

Counting the minimum node weight spanning trees for broadcast transmission in wireless sensor networks

Tańcula J.

Studia Informatica

|

2017

|

Vol. 38, nr 3

125--133

EN

Article presents algorithm optimizing power consumption for broadcast in sensor networks. The broadcast allows of sending data to all ports connected to a given network. Wireless sensor networks are built of distributed measuring devices. Each sensor is an autonomous unit, operating independently of the other. They have limited energy resources. Energy management is of key importance for sensors. In this article, we will create a sensor network model with one broadcast node. For this network we will use an algorithm finding minimum node weight spanning tree for which energy consumption will be the smallest.

PL

Artykuł przedstawia algorytm optymalizacji zużycia energii dla broadcastu w sieciach sensorowych. Transmisja broadcastu pozwala na wysłanie danych do wszystkich portów składających się na sieć. Bezprzewodowe sieci sensorowe zbudowane są z rozproszonych urządzeń pomiarowych. Mają one ograniczone zasoby energii. W tym artykule stworzymy model sieci sensorowej z jednym sensorem broadcastującym. Do tej sieci użyjemy algorytmu znajdującego minimalne spinające drzewo wag, pozwalające na oszczędne wykorzystanie energii sensorów.

5

Typowanie efektywnej lokalizacji miejsca składowania biomasy z wykorzystaniem minimalnego drzewa rozpinającego

Duczkowska-Kądziel A.

Logistyka

|

2014

|

nr 6

PL

W pracy przedstawiono problematykę dotyczącą możliwych sposobów określenia optymalnej lokalizacji składowania biomasy, z wykorzystaniem szacowania jej potencjału energetycznego. Przedstawiono możliwość rozbudowania algorytmu szacowania o analizę znajdowania optymalnego miejsca składowania pozyskanej biomasy na przykładzie województwa opolskiego. Znaleziono minimalne drzewo rozpinające i minimalną sumę wag krawędzi reprezentujących drogi łączące poszczególne miejscowości. Opisano również możliwości dalszej rozbudowy algorytmu, z wykorzystaniem teorii grafów, ze względu na możliwość prowadzenia analizy wielokryterialnej.

EN

The paper deals with the topics related to estimation of energy potential offered by biomass along with the method for determination of theoretical and technical potentials. The attention is also focused at the possibility to extend the algorithm with the function that enables searching for an optimized site for biomass storage, where a certain country of the Opole province serves as an example. Finally, the Minimum Spanning Tree (MST) is found with the minimum sum of weight coefficients assigned to the graph edges standing for routes that interconnect specific places. Opportunities for further extension of the algorithm are also outlined where the theory of graphs can be applied to enable multi-criteria analyzes of the graph.

6

Segmentacja obrazów obiektów w postaci skupisk na przykładzie obrazów kometowych

Bal A.

Pomiary Automatyka Kontrola

|

2012

|

R. 58, nr 1

55-58

PL

W pracy przedstawiono propozycję metody segmentacji obiektów będących skupiskami, przykładem takich obiektów są tzw. komety będące wynikiem jednokomórkowej elektroforezy żelowej. Prezentacja nowej metody została poprzedzona przedstawieniem wyników segmentacji tych obrazów metodami standardowymi. Opracowana metoda działa dwuetapowo: etap 1. to segmentacja służąca wyznaczeniu fragmentów składowych obiektów, etap 2 wykorzystuje minimalne drzewo rozpinające do określenia zbioru fragmentów tworzących poszczególne obiekty.

EN

This paper deals with the problem of segmentation of aggregate objects i.e. objects which are formed by the set of unconnected elements smaller than the object. Images of such objects are very difficult to be segmented. An example of this type of objects are "comet" from Single Cell Gel Electrophoresis images (also called comet assay images). In comet assay images the comet region is formed by unconnected fragments of DNA (Fig. 1). Due to unsatisfying results of comet segmentation by stan-dard methods (Figs. 2and 3) a new, two-stage method for segmentation of such images has been developed. The first stage is image segmentation whose result is a set of comet elements ei representing DNA fragments. In the second stage the minimum spanning trees Tp are created - graph vertexes vi represent elements ei, while length dij of edge eij between vertexes vi and vj is equal to the minimum distance between pixels of elements ei and ei. Then for each connected tree Tp its convex hull defining the region of comet Kp (Fig. 4) is created. In case of defects appearing in comet images (Fig. 5) the incorrect region can be rejected e.g. by use of geometrical features describing regions.

7

Grafowa metoda segmentacji obiektów w postaci skupisk na przykładzie obrazów kometowych

Bal A.

Pomiary Automatyka Kontrola

|

2012

|

R. 58, nr 4

313-315

PL

W pracy przedstawiono propozycję metody segmentacji obiektów będących skupiskami - przykładem takich obiektów są tzw. komety, które są wynikiem jednokomórkowej elektroforezy żelowej. Opracowana metoda działa dwuetapowo: etap 1. to segmentacja służąca wyznaczeniu elementów składowych należących do obiektów, etap 2 wykorzystuje minimalne drzewo rozpinające do określenia zbioru elementów tworzących poszczególne obiekty, obszar poszczególnych obiektów wyznaczany jest jako otoczka wypukła odpowiedniego drzewa rozpinającego.

EN

This paper deals with a problem of segmentation of aggregate objects, that is objects which are formed by a set of unconnected elements smaller than the object itself. Images of such a type of objects are very difficult for segmentation. An example of this type of objects are "comets" (Fig. 1, left column) from Single Cell Gel Electrophoresis images (also called comet assay images). In comet assay images the comet region is formed by unconnected fragments of DNA. Because of not satisfying results of comet segmentation with use of the standard methods, a new method for segmentation of such images was developed. The new method works in two stages. The first stage is the image segmentation-for comets the Bernsen binarization method (Eqs. (1) and (2)) with median filtering of the obtained results was chosen-the result of this stage is a set of comet elements ei which represent DNA fragments (Fig. 1, the 2nd column). In the second stage the minimum spanning trees Tp are created (Fig. 1, 3th column)-graph vertexes vi represent elements ei, and length dij of edge eij between vertexes vi and vj is equal to the closest distance between pixels of elements ei and ej-then for each connected tree Tp its convex hull which defines the region of comet Kp (Fig. 1, the 4th column) is created. In case of defects appearing in comet images, the incorrect region can be rejected e.g. by use of geometrical or photometrical features of the regions.

8

A note on the computation of ordered supported non-dominated solutions in the bi-criteria minimum spanning tree problems

Silva C. G., Cli'maco J. C. N.

Journal of Telecommunications and Information Technology

|

2007

|

nr 4

11-15

EN

This paper presents a new procedure for computing the set of supported non dominated solutions of bi-criteria minimum spanning tree problems in ordered manner. The procedure is based on the systematic detection of edges which must be replaced in one efficient solution to obtain the adjacent one, in the criteria space. This new approach avoids solving unnecessary problems and makes use of previous computations.

9

Evolutionary approach to constrained minimum spanning tree problem - commercial software based application

Pagacz A., Raidl G., Zawiślak S.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

z. 156

331-341

EN

The constrained minimum spanning tree problem is considered in the paper. We assume that the degree of any vertex should not exceed a particular constraint d. In this formulation the problem turns into NP-hard one, therefore the evolutionary approach is applicable. The edge set representation of a chromosome was utilized for a tree in the algorithm. The evolutionary algorithm was worked out and the related computer program has been written. Interfaces between the core program and MS Visio as well as the data base system were prepared. The results obtained by means of the system are shown.

10

Optimisation of water distribution networks design by minimizing the total length

Lahiouel Y., Chaoui K., Khezzar L., Haddad A., Azari Z.

Engineering Transactions

|

2005

|

Vol. 53, iss. 2

165-183

EN

The aim of the present work is to establish a new algorithm for the optimization of the design of water distribution networks. The proposed algorithm makes it possible to connect the nodes and the sources using the shortest path to obtain a final looped configuration. A novel method, the "minimal length algorithm", is proposed. It uses the advantages of existing methods and exceeds their limitations. Some of the well-known existing methods are the shortest path algorithm, the minimum spanning tree algorithm and a novel method published previously. The developed algorithm is implemented into a user-friendly interactive computer program which allows the design of looped systems with minimal length ensuring least cost, reliability of the network and hence the availability of water.

11

Estymacja długości połączeń w układach VLSI

Kos A., Nagórny Z.

Elektronika : konstrukcje, technologie, zastosowania

|

2005

|

Vol. 46, nr 11

47-49

PL

Znane są różne sposoby estymacji długości połączeń w układach VLSI. Nie zawsze istnieje zgodność między wartością estymowanej długości połączeń a rzeczywistą długością połączeń po ich wyznaczeniu. Przedstawiono sposób wyznaczenia współczynników korygujących wartość estymowanej długości połączeń, w zależności od liczby końcówek w danym węźle układu elektronicznego. Określono wartości współczynników dla dwóch sposobów estymacji długości połączeń: half-perimeter oraz grafu pełnego. Wartości współczynników wyznaczono na podstawie porównania estymowanej długości połączeń bez współczynników z długością wyznaczoną na podstawie zmodyfikowanego algorytmu Prima, który jest stosowany do prowadzenia połączeń w układach VLSI. Przedstawiono rezultaty rozmieszczania modułów, uzyskane z zastosowaniem otrzymanych współczynników.

EN

The design process of the VLSI circuits requires the use of computer aided design tools. The physical design phases are described: floorplanning, placement and routing. The cell placement is a very important phase of the physical design process. The most commonly used objective of the placement is to minimize the total wire length. Placement algorithms use a wire length estimate to minimize the total wire length, because each intermediate configurations routing takes too much time. The most commonly used methods to estimate the total wire length are halfperimeter and complete graph measures. There is not a good correlation between these estimations and the actual total wire length after routing. In this paper a method to adjust the halfperimeter and complete graph measures using correction factors is presented. The correction factor of the net wire length estimate is a function of the number of net terminals. The actual net wire length is calculated by using a modified Prim algorithm and the Lee algorithm.