Log in

Relevant bibliographies by topics / MST (minimum spanning tree) / Journal articles

To see the other types of publications on this topic, follow the link: MST (minimum spanning tree).

Journal articles on the topic 'MST (minimum spanning tree)'

Author: Grafiati

Published: 4 June 2025

Last updated: 15 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'MST (minimum spanning tree).'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Wang, Xianchao, Shaoyi Li, Changhui Hou, and Guoming Zhang. "Minimum Spanning Tree Method for Sparse Graphs." Mathematical Problems in Engineering 2023 (February 21, 2023): 1–6. http://dx.doi.org/10.1155/2023/8591115.

Full text

Abstract:

The minimum spanning tree (MST) is widely used in planning the most economical network. The algorithm for finding the MST of a connected graph is essential. In this paper, a new algorithm for finding MST is proposed based on a deduced theorem of MST. The algorithm first sorts the edges in the graph according to their weight, from large to small. Next, on the premise of ensuring the connectivity of the graph, it deletes the edges in this order until the number of edges of the graph is equal to the number of vertexes minus 1. Finally, the remaining graph is an MST. This algorithm is equivalent t

APA, Harvard, Vancouver, ISO, and other styles

2

Dili, Yusufiani Nurlinawati. "PENYELESAIAN MASALAH TRANSPORTASI UNTUK MENCARI SOLUSI OPTIMAL DENGAN PENDEKATAN MINIMUM SPANNING TREE (MST) MENGGUNAKAN ALGORITMA KRUSKAL DAN ALGORITMA PRIM." KUBIK: Jurnal Publikasi Ilmiah Matematika 6, no. 1 (2021): 44–50. http://dx.doi.org/10.15575/kubik.v6i1.13907.

Full text

Abstract:

Penelitian ini membahas tentang penyelesaian masalah transportasi dengan pendekatan Minimum Spanning Tree (MST) menggunakan algoritma Kruskal dan algoritma Prim untuk mencari solusi optimal. Algoritma Kruskal dan algoritma Prim merupakan algoritma dalam teori graf untuk mencari Minimum Spanning Tree (MST). Langkah algoritma Kruskal yaitu mengurutkan biaya dari yang terkecil hingga terbesar. Selanjutnya, pilih biaya yang paling terkecil. Kemudian, lakukan perhitungan dengan melihat sumber persediaan dan permintaan di setiap tujuan sampai semuanya terpenuhi, sehingga terlihat bentuk Minimum Span

APA, Harvard, Vancouver, ISO, and other styles

3

Chittaranjan, Mohapatra, Adhikari Nibedita, N. Bhramar Ray B, Nayak Biswojit, and Kumar Dash Akshaya. "AMST: Accelerated Minimum Spanning Tree for Scalable Data." Indian Journal of Science and Technology 16, no. 37 (2023): 3110–20. https://doi.org/10.17485/IJST/v16i37.1420.

Full text

Abstract:

Abstract <strong>Objectives:</strong> A traditional Minimum Spanning Tree (MST) is quite complex for large datasets concerning time and space complexities. So an Accelerated MST (AMST) is proposed for scalable data. <strong>Methods:</strong> AMST uses the k-means clustering to divide large data into a bunch of small-size data. The Delaunay Triangulation is applied to find the relationship among the data in O(nlogn) time for n points as compared to earlier approaches. A mid-point heuristic is designed to combine all clustered MSTs to get the MST for the original data. A refinemen

APA, Harvard, Vancouver, ISO, and other styles

4

LIU, WEI, and CHENGJING YANG. "FUZZY RANDOM DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM." International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 15, supp02 (2007): 107–15. http://dx.doi.org/10.1142/s0218488507004649.

Full text

Abstract:

The degree-constrained minimum spanning tree problem (dc-MST) is to find a minimum spanning tree of the given graph, subject to constraints on node degrees. This paper investigates the dc-MST problem with fuzzy random weights. Three concepts are presented: expected fuzzy random dc-MST, (α,β)-dc-MST and the most chance dc-MST according to different optimization requirement. Correspondingly, by using the concepts as decision criteria, three fuzzy random programming models for dc-MST are given. Finally, a hybrid intelligent algorithm is designed to solve these models, and some numerical examples

APA, Harvard, Vancouver, ISO, and other styles

5

Xu, Lantian, Dong Wen, Lu Qin, et al. "Minimum Spanning Tree Maintenance in Dynamic Graphs." Proceedings of the ACM on Management of Data 3, no. 1 (2025): 1–24. https://doi.org/10.1145/3709704.

Full text

Abstract:

Minimum Spanning Tree (MST) is a fundamental structure in graph analytics and can be applied in various applications. The problem of maintaining MSTs in dynamic graphs is significant, as many real-world graphs are frequently updated. Existing studies on MST maintenance primarily focus on theoretical analysis and lack practical efficiency. In this paper, we propose a novel algorithm to maintain MST in dynamic graphs, which achieves high practical efficiency. In addition to the tree structure, our main idea is to maintain a replacement edge for each tree edge. In this way, the tree structure can

APA, Harvard, Vancouver, ISO, and other styles

6

Adasme, Pablo, and Ali Dehghan Firoozabadi. "Degree-Constrained k -Minimum Spanning Tree Problem." Complexity 2020 (November 8, 2020): 1–25. http://dx.doi.org/10.1155/2020/7628105.

Full text

Abstract:

Let G V , E be a simple undirected complete graph with vertex and edge sets V and E , respectively. In this paper, we consider the degree-constrained k -minimum spanning tree (DC k MST) problem which consists of finding a minimum cost subtree of G formed with at least k vertices of V where the degree of each vertex is less than or equal to an integer value d ≤ k − 2 . In particular, in this paper, we consider degree values of d ∈ 2,3 . Notice that DC k MST generalizes both the classical degree-constrained and k -minimum spanning tree problems simultaneously. In particular, when d = 2 , it redu

APA, Harvard, Vancouver, ISO, and other styles

7

Sembiring, R. R., Sufri, and C. Multahadah. "Penerapan Algoritma Prim dalam Menentukan Minimum Spanning Tree (MST) (Studi Kasus: Jaringan Pipa PDAM Tirta Muaro Jambi)." JURNAL ILMIAH MATEMATIKA DAN TERAPAN 19, no. 1 (2022): 58–71. http://dx.doi.org/10.22487/2540766x.2022.v19.i1.15890.

Full text

Abstract:

Salah satu contoh masalah dalam graf adalah pencarian pohon merentang. Terdapat dua kasus yang pada umumnya dibahas dalam pencarian pohon merentang, yaitu pohon merentang maksimum dan pohon merentang minimum. Ada beberapa algoritma yang dapat digunakan untuk mencari pohon merentang minimum dari sebuah graf berbobot atau dikenal dengan istilah pencarian Minimum Spanning Tree (MST). Pada penelitian ini dilakukan pencarian Minimum Spanning Tree pada jaringan pipa air PDAM pada perumahan mendalo asri, menggunakan Algoritma Prim. Pencarian dilakukan secara manual dan menggunakan software TORA. Peng

APA, Harvard, Vancouver, ISO, and other styles

8

Moqbel Hassan ALZUBAYDI, Nadia. "DESIGN AND IMPLEMENTATION OF KRUSKAL'S MINIMUM SPANNING TREE ALGORITHM IN C++." MINAR International Journal of Applied Sciences and Technology 2, no. 3 (2020): 35–45. http://dx.doi.org/10.47832/2717-8234.3-2.6.

Full text

Abstract:

The traditional algorithms (Prim) or (Kruskal) are able to obtain A minimum spanning tree (MST) in undirected graph easily. But many algorithms have been proposed for the purpose of obtaining spanning trees in undirected graph, these algorithms are considering the complexities of time and space. Some algorithms are generating spanning trees by using some basic cuts or circuits. In this process, the tree's cost is not considered. In this paper we will describe an algorithm for generating spanning trees in a graph of increasing cost, so we will get many possibilities, such as determining the k-t

APA, Harvard, Vancouver, ISO, and other styles

9

Gombos, Daniel, James A. Hansen, Jun Du, and Jeff McQueen. "Theory and Applications of the Minimum Spanning Tree Rank Histogram." Monthly Weather Review 135, no. 4 (2007): 1490–505. http://dx.doi.org/10.1175/mwr3362.1.

Full text

Abstract:

Abstract A minimum spanning tree (MST) rank histogram (RH) is a multidimensional ensemble reliability verification tool. The construction of debiased, decorrelated, and covariance-homogenized MST RHs is described. Experiments using Euclidean L2, variance, and Mahalanobis norms imply that, unless the number of ensemble members is less than or equal to the number of dimensions being verified, the Mahalanobis norm transforms the problem into a space where ensemble imperfections are most readily identified. Short-Range Ensemble Forecast Mahalanobis-normed MST RHs for a cluster of northeastern U.S.

APA, Harvard, Vancouver, ISO, and other styles

10

Siahaan, Charmenita Enjellina, and Niken Rarasati. "Penerapan Algoritma Reverse-Delete dalam Menentukan Minimum Spanning Tree Pada Jaringan Pipa PERUMDA Air Minum Tirta Mayang di Perumahan Sunderland." Technologica 3, no. 1 (2024): 10–19. http://dx.doi.org/10.55043/technologica.v3i1.139.

Full text

Abstract:

Konstruksi jaringan perpipaan adalah bagian termahal bagi sistem distribusi air. Oleh karena itu, pendistribusian air bersih merupakan persoalan yang perlu diperhatikan. Rencana yang tepat diperlukan agar dapat mengefisiensikan pemakaian pipa dan dana yang dikeluarkan untuk pemasangan pipa pada pendistribusian air PERUMDA Air Minum Tirta Mayang. Upaya untuk mengoptimalkan panjang jaringan pipa air PERUMDA Air Minum Tirta Mayang dapat dilakukan dengan mencari Minimum Spanning Tree (MST). Pada penelitian ini dilakukan pencarian Minimum Spanning Tree (MST) dari jaringan pipa tersier PERUMDA Air M

APA, Harvard, Vancouver, ISO, and other styles

11

Yıldırım, Emircan, Kerim Eser Afşar, and Ahmet Aydın Arı. "Sectoral Analysis of the Cryptocurrency Market Using Minimum Spanning Tree." İzmir İktisat Dergisi 40, no. 2 (2024): 400–409. https://doi.org/10.24988/ije.1514118.

Full text

Abstract:

This study examined the interaction dynamics and clustering characteristics of cryptocurrencies using MST (Minimum Spanning Tree) analysis based on the daily closing prices of 67 cryptocurrencies traded on Binance. The study included ten cryptocurrencies from the gaming sector and 56 high-market-cap cryptocurrencies. While cryptocurrencies have been analysed from various perspectives using MST in the literature, sectoral analysis has been neglected. This study focused on the categorization of cryptocurrencies and directly on crypto games. According to the MST analysis, crypto games and decentr

APA, Harvard, Vancouver, ISO, and other styles

12

Lastri, Devi, Masriani, Nadia W, Parizal Hidayatullah, Wahyu Ulfayandhie Misuki, and Mamika Ujianita Romdhini. "Meminimalisir Biaya Pembuatan Saluran Air PDAM Di Wilayah KLU Menggunakan Algoritma Kruskal." EIGEN MATHEMATICS JOURNAL 1, no. 1 (2019): 27. http://dx.doi.org/10.29303/emj.v1i1.22.

Full text

Abstract:

The kruskal algorithm is an algorithm to search for minimum spanning trees directly based on the general MST (Minimum Spanning Tree) algorithm. In the kruskal algorithm, the sides in the graph are sorted first based on their weight from small to large. The kruskal algorithm in the search for a minimum spanning tree can be applied to the distribution of clean water of PDAM in North Lombok district. This problem is intended to get the shortest route for PDAM water distribution in North Lombok district in order to minimize costs.

APA, Harvard, Vancouver, ISO, and other styles

13

Akhirina, Tri Yani, and Thomas Afrizal. "Pendekatan Matriks Ketetanggaan Berbobot untuk Solusi Minimum Spanning Tree (MST)." STRING (Satuan Tulisan Riset dan Inovasi Teknologi) 4, no. 3 (2020): 280. http://dx.doi.org/10.30998/string.v4i3.5900.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Çalışkan, Murat, and Berk Anbaroğlu. "Geo-MST: A geographical minimum spanning tree plugin for QGIS." SoftwareX 12 (July 2020): 100553. http://dx.doi.org/10.1016/j.softx.2020.100553.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Dutta, S., D. Patra, H. Shankar, and P. Alok Verma. "Development of Gis Tool for the Solution of Minimum Spanning Tree Problem using Prim's Algorithm." ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences XL-8 (November 28, 2014): 1105–14. http://dx.doi.org/10.5194/isprsarchives-xl-8-1105-2014.

Full text

Abstract:

minimum spanning tree (MST) of a connected, undirected and weighted network is a tree of that network consisting of all its nodes and the sum of weights of all its edges is minimum among all such possible spanning trees of the same network. In this study, we have developed a new GIS tool using most commonly known rudimentary algorithm called Prim’s algorithm to construct the minimum spanning tree of a connected, undirected and weighted road network. This algorithm is based on the weight (adjacency) matrix of a weighted network and helps to solve complex network MST problem easily, efficiently

APA, Harvard, Vancouver, ISO, and other styles

16

Zhang, Rener. "The comparison of three MST algorithms." Applied and Computational Engineering 17, no. 1 (2023): 191–97. http://dx.doi.org/10.54254/2755-2721/17/20230939.

Full text

Abstract:

The minimum spanning tree, connecting all the nodes of a connected, weighted graph with the minimum possible total edge weight, is a fundamental concept of graph theory. Thus, how to find the minimum spanning tree (MST) with higher efficiency appears to be crucial. Three kinds of algorithms for this problem have already been developed: Kruskal, Prim, Boruvka. In order to make readers have a better understanding of the three algorithms in the process of studying and teaching, this paper uses the method of comparing to indicate the differences and commonalities between these three algorithms, dr

APA, Harvard, Vancouver, ISO, and other styles

17

Suwardi, Arie Prasetya, Mufti Arifin, and Endah Yuniarti. "“OPTIMASI JARINGAN PADA PANGKALAN UDARA DI INDONESIA MENGGUNAKAN METODE MINIMUM SPANNING TREE”." Jurnal Teknologi Kedirgantaraan 9, no. 2 (2024): 115–26. https://doi.org/10.35894/jtk.v9i2.133.

Full text

Abstract:

Pangkalan Angkatan Udara (Lanud) di Indonesia memiliki peran krusial dalam menjaga keamanan dan pertahanan negara, khususnya dalam mendukung operasional TNI Angkatan Udara. Penelitian ini bertujuan untuk mencari jaringan Minimum Spanning Tree antar Pangkalan Udara (Lanud) di Indonesia dengan menggunakan metode Minimum Spanning Tree (MST). Minimum Spanning Tree (MST) digunakan untuk menghubungkan semua Lanud. Dengan menggunakan analisa Metode Minimal Spanning Tree, dapat memberikan solusi optimal dengan menghasilkan total jarak tempuh yang minimal dengan prosedur penghubungan langsung pada titi

APA, Harvard, Vancouver, ISO, and other styles

18

DU, HAI, WEILI WU, ZAIXIN LU, and YINFENG XU. "ON THE STEINER RATIO IN $\mathcal{R}_{n}$." Discrete Mathematics, Algorithms and Applications 03, no. 04 (2011): 473–89. http://dx.doi.org/10.1142/s1793830911001358.

Full text

Abstract:

The Steiner minimum tree and the minimum spanning tree are two important problems in combinatorial optimization. Let P denote a finite set of points, called terminals, in the Euclidean space. A Steiner minimum tree of P, denoted by SMT(P), is a network with minimum length to interconnect all terminals, and a minimum spanning tree of P, denoted by MST(P), is also a minimum network interconnecting all the points in P, however, subject to the constraint that all the line segments in it have to terminate at terminals. Therefore, SMT(P) may contain points not in P, but MST(P) cannot contain such ki

APA, Harvard, Vancouver, ISO, and other styles

19

Mary, Francis Remigius Perpetua, Swaminathan Mohanaselvi, and Said Broumi. "A solution approach to minimum spanning tree problem under fermatean fuzzy environment." Bulletin of Electrical Engineering and Informatics 12, no. 3 (2023): 1738–46. http://dx.doi.org/10.11591/eei.v12i3.4794.

Full text

Abstract:

In classical graph theory, the minimal spanning tree (MST) is a subgraph with no cycles that connects each vertex with minimum edge weights. Calculating minimum spanning tree of a graph has always been a common problem throughout ages. Fuzzy minimum spanning tree (FMST) is able to handle uncertainty existing in edge weights for a fuzzy graph which occurs in real world situations. In this article, we have studied the MST problem of a directed and undirected fuzzy graph whose edge weights are represented by fermatean fuzzy numbers (FFN). We focus on determining an algorithmic approach for solvin

APA, Harvard, Vancouver, ISO, and other styles

20

Burt, Christina, Alysson Costa, and Charl Ras. "Algorithms for the power-p Steiner tree problem in the Euclidean plane." Revista de Informática Teórica e Aplicada 25, no. 4 (2018): 28. http://dx.doi.org/10.22456/2175-2745.80525.

Full text

Abstract:

We study the problem of constructing minimum power-$p$ Euclidean $k$-Steiner trees in the plane. The problem is to find a tree of minimum cost spanning a set of given terminals where, as opposed to the minimum spanning tree problem, at most $k$ additional nodes (Steiner points) may be introduced anywhere in the plane. The cost of an edge is its length to the power of $p$ (where $p\geq 1$), and the cost of a network is the sum of all edge costs. We propose two heuristics: a ``beaded" minimum spanning tree heuristic; and a heuristic which alternates between minimum spanning tree construction and

APA, Harvard, Vancouver, ISO, and other styles

21

D, Vijayalakshmi, and Kalaivani R. "FUZZY SHORTEST ROUTE ALGORITHM FOR TELEPHONE LINE CONNECTION USING THE LC-MST ALGORITHM." Kongunadu Research Journal 2, no. 2 (2015): 37–39. http://dx.doi.org/10.26524/krj93.

Full text

Abstract:

In computer science, there are many algorithms that finds a minimum spanning tree for a connected weighted undirected fuzzy graph. The minimum length (or cost) spanning tree problem is one of the nicest and simplest problems in network optimization, and it has a wide variety of applications. The problem is tofind a minimum cost (or length) spanning tree in G. Applications include the design of various types of distribution networks in which the nodes represent cities, centers etc.; and edges represent communication links (fiber glass phone lines, data transmission lines, cable TV lines, etc.),

APA, Harvard, Vancouver, ISO, and other styles

22

Francis, Remigius Perpetua Mary, Mohanaselvi Swaminathan, and Broumi Said. "A solution approach to minimum spanning tree problem under fermatean fuzzy environment." Bulletin of Electrical Engineering and Informatics 12, no. 3 (2023): 1738~1746. https://doi.org/10.11591/eei.v12i3.4794.

Full text

Abstract:

In classical graph theory, the minimal spanning tree (MST) is a subgraph with no cycles that connects each vertex with minimum edge weights. Calculating minimum spanning tree of a graph has always been a common problem throughout ages. Fuzzy minimum spanning tree (FMST) is able to handle uncertainty existing in edge weights for a fuzzy graph which occurs in real world situations. In this article, we have studied the MST problem of a directed and undirected fuzzy graph whose edge weights are represented by fermatean fuzzy numbers (FFN). We focus on determining an algorithmic approach for solvin

APA, Harvard, Vancouver, ISO, and other styles

23

Devillers, J., and J. C. Dore. "Heuristic potency of the minimum spanning tree (MST) method in toxicology." Ecotoxicology and Environmental Safety 17, no. 2 (1989): 227–35. http://dx.doi.org/10.1016/0147-6513(89)90042-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Dr., V. Raghunatha Reddy. "FUZZY LOGIC BASED CLUSTERING ALGORITHM WITH MINIMUM SPANNING TREE IN WIRELESS SENSOR NETWORK." INTERNATIONAL JOURNAL OF ENGINEERING SCIENCES & RESEARCH TECHNOLOGY 9, no. 3 (2020): 104–15. https://doi.org/10.5281/zenodo.7027366.

Full text

Abstract:

Wireless Sensor Network (WSN) comprises of the resource constrained sensor nodes that are predictable to work autonomously for long-period of time. Because of the restricted accessibility of the power supply, the main worry in the WSN is energy preservation. Usually, the Minimum Spanning Tree (MST) utilized the optimum data aggregation tree for an energy-efficient routing. Earlier the consumption of energy condensed through the hop basis data transmission includes the help of the Prim’s Algorithm. In this article, Fuzzy Logic clustering based algorithm utilized to create clusters & t

APA, Harvard, Vancouver, ISO, and other styles

25

Tomeczek, Artur F. "A minimum spanning tree analysis of the Polish stock market." Journal of Economics and Management 44 (2022): 420–45. http://dx.doi.org/10.22367/jem.2022.44.17.

Full text

Abstract:

Aim/purpose – This article aims to explore the network topology of the stock market in Poland during the COVID-19 pandemic. Design/methodology/approach – Kruskal’s algorithm was used to find the minimum spanning trees (MST) of three undirected correlation networks: MST1 (December 2019 – August 2021), MST2 (February 2020 – April 2020), and MST3 (June 2021 – August 2021). There were123 firms included in all three networks representing three key indexes (WIG20, mWIG40, and sWIG80). Findings – The comovements of stock prices varied between various periods of the pandemic. The most central firms in

APA, Harvard, Vancouver, ISO, and other styles

26

Berouaga, Younes, Cherif El Msiyah, and Jaouad Madkour. "Portfolio Optimization Using Minimum Spanning Tree Model in the Moroccan Stock Exchange Market." International Journal of Financial Studies 11, no. 2 (2023): 53. http://dx.doi.org/10.3390/ijfs11020053.

Full text

Abstract:

Portfolio optimization is a pertinent topic of significant importance in the financial literature. During the portfolio construction, an investor confronts two important steps: portfolio selection and portfolio allocation. This article seeks to investigate portfolio optimization based on the Minimum Spanning Tree (MST) method applied on the Moroccan All Shares Index (MASI) historical stock log returns covering the period from 2 January 2013 to 27 October 2022 allowing us to build two portfolios: MST-Portfolio and MST-Portfolio 2. Portfolio selection was carried out for MST-Portfolio and MST-Po

APA, Harvard, Vancouver, ISO, and other styles

27

Gao, Qiang, Qin-Qin Gao, Zhong-Yang Xiong, Yu-Fang Zhang, and Min Zhang. "A Novel Minimum Spanning Tree Clustering Algorithm Based on Density Core." Computational Intelligence and Neuroscience 2022 (October 5, 2022): 1–17. http://dx.doi.org/10.1155/2022/8496265.

Full text

Abstract:

Clustering analysis is an unsupervised learning method, which has applications across many fields such as pattern recognition, machine learning, information security, and image segmentation. The density-based method, as one of the various clustering algorithms, has achieved good performance. However, it works poor in dealing with multidensity and complex-shaped datasets. Moreover, the result of this method depends heavily on the parameters we input. Thus, we propose a novel clustering algorithm (called the MST-DC) in this paper, which is based on the density core. Firstly, we employ the revers

APA, Harvard, Vancouver, ISO, and other styles

28

Andersen, Patrick J., and Charl J. Ras. "Algorithms for Euclidean Degree Bounded Spanning Tree Problems." International Journal of Computational Geometry & Applications 29, no. 02 (2019): 121–60. http://dx.doi.org/10.1142/s0218195919500031.

Full text

Abstract:

Given a set of points in the Euclidean plane, the Euclidean [Formula: see text]-minimum spanning tree ([Formula: see text]-MST) problem is the problem of finding a spanning tree with maximum degree no more than [Formula: see text] for the set of points such the sum of the total length of its edges is minimum. Similarly, the Euclidean [Formula: see text]-minimum bottleneck spanning tree ([Formula: see text]-MBST) problem, is the problem of finding a degree-bounded spanning tree for a set of points in the plane such that the length of the longest edge is minimum. When [Formula: see text], these

APA, Harvard, Vancouver, ISO, and other styles

29

P., Lakshmi, Ramyachitra D., and Pavithravishalini E. "Motif Discovery of Protein-Protein Interaction using Minimum Spanning Tree." International Journal of Engineering and Advanced Technology (IJEAT) 9, no. 3 (2020): 990–94. https://doi.org/10.35940/ijeat.B4576.029320.

Full text

Abstract:

In protein Interaction Networks, counting subgraph is a tedious task. From the list of non induced occurrence of the subgraph, motif topology calculated by using Combi Motif and Slider techniques. But, this approach was taken more time to execute. To reduce the execution time, the minimum weight value between the nodes, the Minimum spanning tree concept proposed. Prim’s method implemented with the greedy technique (as Kruskal’s algorithm) to calculate the minimum path between the nodes in the Protein interaction network. This technique uses to compare the similarity of the minimum

APA, Harvard, Vancouver, ISO, and other styles

30

DAS, SAJAL K., and PAOLO FERRAGINA. "AN EREW PARM ALGORITHM FOR UPDATING MINIMUM SPANNING TREES." Parallel Processing Letters 09, no. 01 (1999): 111–22. http://dx.doi.org/10.1142/s012962649900013x.

Full text

Abstract:

We propose a parallel algorithm for the EREW PRAW model that maintains a minimum spanning tree (MST) of an undirected graph under single edge insertions and deletions. For a graph of n nodes and m edges, each update requires O( log n) time and O(m 2/3 log n) work. This is a substantial improvement over the known bounds on the work complexity. Our algorithm uses a partition of the MST, similar to the sequential approach due to Frederickson [6], and also employs a novel data structure for efficiently managing edge insertions in parallel.

APA, Harvard, Vancouver, ISO, and other styles

31

Assuncao, Renato, Marcos Neves, Gilberto Camara, and Corina Freitas. "Efficient regionalization techniques for socio-economic geographical units using minimum spanning trees." International Journal of Geographical Information Science 20, no. 7 (2007): 797–811. https://doi.org/10.1080/13658810600665111.

Full text

Abstract:

Regionalization is a classification procedure applied to spatial objects with an areal representation, which groups them into homogeneous contiguous regions. This paper presents an efficient method for regionalization. The first step creates a connectivity graph that captures the neighbourhood relationship between the spatial objects. The cost of each edge in the graph is inversely proportional to the similarity between the regions it joins. We summarize the neighbourhood structure by a minimum spanning tree (MST), which is a connected tree with no circuits. We partition the MST by successive

APA, Harvard, Vancouver, ISO, and other styles

32

Sarvade, Akanksha. "Analysis between Prims and Kruskal’s Algorithm." International Journal for Research in Applied Science and Engineering Technology 12, no. 11 (2024): 2464–67. https://doi.org/10.22214/ijraset.2024.65593.

Full text

Abstract:

The project is an analytical comparison between two algorithms that is Prim’s algorithm and Kruskal’s algorithm in MST (minimum spanning tree). Both the algorithms aim to connect all the vertices based on their weight but differ in implementation and approach. Prim’s algorithm is Greedy algorithm which makes the minimum spanning tree according to their incremental weight It starts with one vertex and expands its MST, it always selects smallest edge in MST. Kruskal’s algorithm is also greedy algorithm but its approaches differently. It starts with all the vertices and no edge and it adds edge w

APA, Harvard, Vancouver, ISO, and other styles

33

Abbasi, M. J., Muhammad Shafie Bin Abd Latiff, Hassan Chizari, and N. Fisal. "Game Theory Based Construction Efficient Topology in Wireless Sensor Networks." Mathematical Problems in Engineering 2015 (2015): 1–12. http://dx.doi.org/10.1155/2015/754940.

Full text

Abstract:

Topology control is one of the most important techniques used in wireless sensor networks; to some extent it can reduce energy consumption in which each node is capable of minimizing its transmission power level while preserving network connectivity. Reducing energy consumption has been addressed through different aspects till now. In this paper, we present a minimum spanning tree- (MST-) based algorithm, called noncooperative minimum spanning tree (NMST), for topology control in wireless multihop networks. In this algorithm, each node constructs its minimum power-cost spanning tree which is a

APA, Harvard, Vancouver, ISO, and other styles

34

ZHOU, GENGUI, ZHENYU CAO, ZHIQING MENG, and JIAN CAO. "GA-BASED ALTERNATIVE APPROACHES FOR THE DEGREE-CONSTRAINED SPANNING TREE PROBLEM." International Journal of Pattern Recognition and Artificial Intelligence 23, no. 01 (2009): 129–44. http://dx.doi.org/10.1142/s0218001409006989.

Full text

Abstract:

The degree-constrained minimum spanning tree (dc-MST) problem is of high practical importance. Up to now there are few effective algorithms to solve this problem because of its NP-hard complexity. More recently, a genetic algorithm (GA) approach for this problem was tried by using Prüfer number to encode a spanning tree. The Prüfer number is a skillful encoding for tree but not efficient enough to deal with the dc-MST problem. In this paper, a new tree-based encoding is developed directly based on the tree structure. We denote it as tree-based permutation encoding and apply it to the dc-MST pr

APA, Harvard, Vancouver, ISO, and other styles

35

Lv, Xiaobo, Yan Ma, Xiaofu He, Hui Huang, and Jie Yang. "CciMST: A Clustering Algorithm Based on Minimum Spanning Tree and Cluster Centers." Mathematical Problems in Engineering 2018 (December 17, 2018): 1–14. http://dx.doi.org/10.1155/2018/8451796.

Full text

Abstract:

The minimum spanning tree- (MST-) based clustering method can identify clusters of arbitrary shape by removing inconsistent edges. The definition of the inconsistent edges is a major issue that has to be addressed in all MST-based clustering algorithms. In this paper, we propose a novel MST-based clustering algorithm through the cluster center initialization algorithm, called cciMST. First, in order to capture the intrinsic structure of the data sets, we propose the cluster center initialization algorithm based on geodesic distance and dual densities of the points. Second, we propose and demon

APA, Harvard, Vancouver, ISO, and other styles

36

PRASAD, MUNAGA V. N. K., P. SWATHI, C. R. RAO, and B. L. DEEKSHATULU. "MINIMUM SPANNING TREE (MST) BASED TECHNIQUES FOR GENERATION OF CANCELABLE FINGERPRINT TEMPLATES." International Journal of Pattern Recognition and Artificial Intelligence 28, no. 06 (2014): 1456013. http://dx.doi.org/10.1142/s0218001414560138.

Full text

Abstract:

The biometric community is faced with the difficult problem of protection of the original biometric template. One way of doing this is using a cancelable biometric method, which transforms original biometric template in a noninvertible way and uses the transformed template to verify a person's identity. In this paper, we propose two novel representation methods for fingerprint minutiae. Proposed methods based on this representation are simple to generate cancelable templates without requiring pre-alignment of the fingerprints. The main idea is to generate a minimal spanning tree (MST) for fing

APA, Harvard, Vancouver, ISO, and other styles

37

Kandasamy, Ilanthenral. "Double-Valued Neutrosophic Sets, their Minimum Spanning Trees, and Clustering Algorithm." Journal of Intelligent Systems 27, no. 2 (2018): 163–82. http://dx.doi.org/10.1515/jisys-2016-0088.

Full text

Abstract:

AbstractNeutrosophy (neutrosophic logic) is used to represent uncertain, indeterminate, and inconsistent information available in the real world. This article proposes a method to provide more sensitivity and precision to indeterminacy, by classifying the indeterminate concept/value into two based on membership: one as indeterminacy leaning towards truth membership and the other as indeterminacy leaning towards false membership. This paper introduces a modified form of a neutrosophic set, called Double-Valued Neutrosophic Set (DVNS), which has these two distinct indeterminate values. Its relat

APA, Harvard, Vancouver, ISO, and other styles

38

Zhang, Yuejun, Zhao Pan, Pengjun Wang, and Xiaowei Zhang. "A Low Cost MST-FSM Obfuscation Method for Hardware IP Protection." Journal of Circuits, Systems and Computers 29, no. 13 (2020): 2050208. http://dx.doi.org/10.1142/s0218126620502084.

Full text

Abstract:

Effective resistance to intellectual property (IP) piracy, overproduction and reverse engineering are becoming more and more necessary in the integrated circuit (IC) supply chain. To protect the hardware, the obfuscation methodology hides the original function by adding a large number of redundant states. However, existing hardware obfuscation approaches have hardware overhead and efficiency of obfuscation limitations. This paper proposed a novel methodology for IP security using the minimum spanning tree finite state machine (MST-FSM) obfuscation. In the minimum spanning tree (MST) algorithm,

APA, Harvard, Vancouver, ISO, and other styles

39

Bekti Afriani Pratiwi, Daniel Dharmawan, Muhammad Ilham, Royhan Akmal Firdaus, Tegar Prayoga Putra, and Risty Jayanti. "ANALISIS JARINGAN LISTRIK DI PERUMAHAN CARDJO KM 15 BALIKPAPAN MENGGUNAKAN MINIMUM SPANNING TREE." JURNAL ELEKTROSISTA 11, no. 2 (2024): 148–56. https://doi.org/10.63824/jtep.v11i2.177.

Full text

Abstract:

Optimalisasi jaringan listrik memegang peranan yang sangat krusial. Salah satu disiplin ilmu yang berkontribusi untuk meningkatkan efisiensi jaringan listrik adalah graf. Penelitian ini merupakan studi kasus yang dilakukan di lingkungan perumahan Cardjo KM 15 Balikpapan dengan menganalisis panjang kabel listrik yang terpasang. Untuk memecahkan masalah keoptimuman jaringan listrik digunakan MST (Minimum Spanning Tree) dengan algoritma Prim. Metode Minimum Spanning Tree (MST) digunakan untuk mengoptimalkan jaringan kabel dengan memilih jalur terpendek antar titik-titik penting. Penelitian ini di

APA, Harvard, Vancouver, ISO, and other styles

40

Pattanavichai, Santi. "Comparison on Routing Processing Performance between Shortest Paths Tree (SPT) and Minimum Spanning Tree (MST)." International Review on Computers and Software (IRECOS) 17, no. 2 (2022): 62. http://dx.doi.org/10.15866/irecos.v17i2.22439.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Todeschini, Roberto, and Cecile Valsecchi. "Evaluation of classification performances of minimum spanning trees by 13 different metrics." MATCH Communications in Mathematical and in Computer Chemistry 87, no. 2 (2021): 273–98. http://dx.doi.org/10.46793/match.87-2.273t.

Full text

Abstract:

Minimum Spanning Tree (MST) is a well-known clustering algorithm that provides a graphical tree representation of the objects in a data set by exploiting local information to link each pair of similar objects. The a-posteriori analysis of this tree in terms of nodes and edges provides the basis to derive simple classifiers, namely semi-supervised classification approaches based on the minimum spanning tree approach. In this work, we propose different metrics to evaluate the MST ability to group objects of the same a-priori known classes. The classification capability of the proposed approach,

APA, Harvard, Vancouver, ISO, and other styles

42

Roy, Sharadindu, and Prof Samar Sen Sarma. "AN APPROACH TO GENERATE MST WITHOUT CHECKING CYCLE." INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY 4, no. 2 (2005): 408–18. http://dx.doi.org/10.24297/ijct.v4i2b1.3229.

Full text

Abstract:

Abstract: A minimum spanning tree of an undirected graph can be easily obtained using classical algorithms by Prim or Kruskal. MST generation is a NP hard problem. Now this paper represents an algorithm to find minimum spanning tree without checking cycle. Good time and space complexities are the major concerns of this algorithm. Running Time (complexity) of this algorithm = O(E*log V) (E = edges, V = nodes),which is obviously better than primâ€™s algorithm(complexity- E +Vlog V) . Â This algorithms operate at O(E * log(V)) time, though Primâ€™s can be optimized to O(E + V log V) by using spec

APA, Harvard, Vancouver, ISO, and other styles

43

Wang, Ping, Zheng Wei, Weihong Cui, and Zhiyong Lin. "A MINIMUM SPANNING TREE BASED METHOD FOR UAV IMAGE SEGMENTATION." ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences III-7 (June 7, 2016): 111–17. http://dx.doi.org/10.5194/isprsannals-iii-7-111-2016.

Full text

Abstract:

This paper proposes a Minimum Span Tree (MST) based image segmentation method for UAV images in coastal area. An edge weight based optimal criterion (merging predicate) is defined, which based on statistical learning theory (SLT). And we used a scale control parameter to control the segmentation scale. Experiments based on the high resolution UAV images in coastal area show that the proposed merging predicate can keep the integrity of the objects and prevent results from over segmentation. The segmentation results proves its efficiency in segmenting the rich texture images with good boundary o

APA, Harvard, Vancouver, ISO, and other styles

44

Wang, Ping, Zheng Wei, Weihong Cui, and Zhiyong Lin. "A MINIMUM SPANNING TREE BASED METHOD FOR UAV IMAGE SEGMENTATION." ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences III-7 (June 7, 2016): 111–17. http://dx.doi.org/10.5194/isprs-annals-iii-7-111-2016.

Full text

Abstract:

This paper proposes a Minimum Span Tree (MST) based image segmentation method for UAV images in coastal area. An edge weight based optimal criterion (merging predicate) is defined, which based on statistical learning theory (SLT). And we used a scale control parameter to control the segmentation scale. Experiments based on the high resolution UAV images in coastal area show that the proposed merging predicate can keep the integrity of the objects and prevent results from over segmentation. The segmentation results proves its efficiency in segmenting the rich texture images with good boundary o

APA, Harvard, Vancouver, ISO, and other styles

45

TORKESTANI, JAVAD AKBARI. "A LEARNING AUTOMATA-BASED ALGORITHM TO THE STOCHASTIC MIN-DEGREE CONSTRAINED MINIMUM SPANNING TREE PROBLEM." International Journal of Foundations of Computer Science 24, no. 03 (2013): 329–48. http://dx.doi.org/10.1142/s012905411350007x.

Full text

Abstract:

Min-degree constrained minimum spanning tree (md-MST) problem is an NP-hard combinatorial optimization problem seeking for the minimum weight spanning tree in which the vertices are either of degree one (leaf) or at least degree d ≥ 2. md-MST problem is new to the literature and very few studies have been conducted on this problem in deterministic graph. md-MST problem has several appealing real-world applications. Though in realistic applications the graph conditions and parameters are stochastic and vary with time, to the best of our knowledge no work has been done on solving md-MST problem

APA, Harvard, Vancouver, ISO, and other styles

46

Pagh, Rasmus, Lukas Retschmeier, Hao Wu, and Hanwen Zhang. "Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation." Proceedings of the ACM on Management of Data 3, no. 2 (2025): 1–26. https://doi.org/10.1145/3725240.

Full text

Abstract:

We study the problem of privately releasing an approximate minimum spanning tree (MST). Given a graph G = ( V , E , W ) where V is a set of n vertices, E is a set of m undirected edges, and W ∈ ℝ |E| is an edge-weight vector, our goal is to publish an approximate MST under edge-weight differential privacy, as introduced by Sealfon in PODS 2016, where V and E are considered public and the weight vector is private. Our neighboring relation is 𝓁 ∞ -distance on weights: for a sensitivity parameter Δ ∞ , graphs G = ( V , E , W ) and G' = ( V , E , W ') are neighboring if || W - W '|| ∞ ≤ Δ ∞ ). Exi

APA, Harvard, Vancouver, ISO, and other styles

47

García, C. R., Diego F. Torres, Jia-Ming Zhu-Ge, and Bing Zhang. "Separating Repeating Fast Radio Bursts Using the Minimum Spanning Tree as an Unsupervised Methodology." Astrophysical Journal 977, no. 2 (2024): 273. https://doi.org/10.3847/1538-4357/ad9020.

Full text

Abstract:

Abstract Fast radio bursts (FRBs) represent one of the most intriguing phenomena in modern astrophysics. However, their classification into repeaters and nonrepeaters is challenging. Here, we present the application of the graph theory minimum spanning tree (MST) methodology as an unsupervised classifier of repeater and nonrepeater FRBs. By constructing MSTs based on various combinations of variables, we identify those that lead to MSTs that exhibit a localized high density of repeaters at each side of the node with the largest betweenness centrality. Comparing the separation power of this met

APA, Harvard, Vancouver, ISO, and other styles

48

Rembulan, Glisina Dwinoor, Julliete Angel Luin, Vri Julianto, and Giovandri Septorino. "Optimalisasi Panjang Jaringan Pipa Air Bersih di Dki Jakarta Menggunakan Minimum Spanning Tree." Jurnal INTECH Teknik Industri Universitas Serang Raya 6, no. 1 (2020): 75–87. http://dx.doi.org/10.30656/intech.v6i1.2164.

Full text

Abstract:

Ketahanan air adalah prioritas utama untuk mencapai kedaulatan pangan nasional. Saat ini ketersediaan akses air bersih belum merata. Jaringan pipa air bersih memainkan peran penting untuk menunjang terpenuhinya permintaan air bersih oleh masyarakat. Jaringan pipa air bersih di DKI Jakarta diakomodasi oleh PT Aetra Air Jakarta (AETRA) dan PT PAM Lyonnaise Jaya (PALYJA). Minimum Spanning Tree (MST) merupakan metode yang digunakan untuk meminimalkan biaya yang dikeluarkan dengan mengoptimalkan jarak. Metode MST digunakan untuk mengoptimalkan panjang jaringan pipa air bersih di DKI Jakarta sehingg

APA, Harvard, Vancouver, ISO, and other styles

49

Gulista, Khan1 Gaurav Bathla2 and Wajid Ali 3. "Minimum Spanning Tree based Routing Strategy for Homogeneous WSN." International Journal on Cloud Computing: Services and Architecture(IJCCSA) 1, August (2018): 01–08. https://doi.org/10.5281/zenodo.1451042.

Full text

Abstract:

A Wireless Sensor Network (WSN) is composed of sensor nodes spread over the field to sense the data. The sensed data must be gathered & transmitted to Base Station (BS) for end user queries. The used sensor nodes being in- expensive having low computation power & limited energy so are not as much reliable as their expensive macro sensor counter parts but their size and cost enable hundred to thousand of micro sensors to achieve high quality fault tolerant system. In an environment where in each round all sensor nodes have to send data to base station, it is required to effectively util

APA, Harvard, Vancouver, ISO, and other styles

50

Li, Bo, Xiaowei Wu, Chenyang Xu, and Ruilong Zhang. "Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 5 (2023): 5730–38. http://dx.doi.org/10.1609/aaai.v37i5.25711.

Full text

Abstract:

Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than ((1-o(1)) ln k)-approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting a

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!