Log in

Relevant bibliographies by topics / MST (minimum spanning tree)

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers
Reports

Academic literature on the topic 'MST (minimum spanning tree)'

Author: Grafiati

Published: 4 June 2025

Last updated: 6 July 2025

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.

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

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 to an inverse Kruskal algorithm. For sparse graphs, the proposed algorithm has higher efficiency than the Kruskal algorithm. Experiments and analysis verify the effectiveness of the algorithm proposed in this paper. The algorithm provides a better choice for finding the MST of the sparse graph.

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 Spanning Tree (MST) dari algoritma Kruskal. Sedangkan langkah algoritma Prim yaitu dengan memilih sembarang titik atau sumber. Selanjutnya, pilih active edge dengan biaya terkecil. Kemudian, lakukan perhitungan dengan melihat sumber persediaan dan permintaan di setiap tujuan sampai semuanya terpenuhi, sehingga terlihat bentuk Minimum Spanning Tree (MST) dari algoritma Prim. Bentuk dari Minimum Spanning Tree (MST) menghasilkan solusi yang optimal. Dari hasil penelitian ini, pendekatan Minimum Spanning Tree (MST) dengan algoritma Prim yang lebih unggul.

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 refinement process is used for any mislaid of minimum weight edges. <strong>Findings:</strong> Several desirable properties of the AMST have been developed and compared with the results of existing literature. AMST is quite competitive in terms of time complexities, least weight error rate and accuracy for both large and small-size datasets. The mathematical analysis of the time complexity O(nlogn) proves that the proposed AMST has a 95% faster execution time than others. The proposed AMST has the least Weight Error Rate than other approaches which indicates that the cost is close to the exact Algorithms. The accuracy of the AMST is an average of 93% in different clustering accuracy indices which is similar to other approaches. <strong>Novelty:</strong> The execution time and accuracy prove that a faster MST can be developed to construct pins wire length routing in the promising field of VLSI (Very Large-Scale Integration) physical design. <strong>Keywords:</strong> MST; Clustering; Delaunay Triangulation; Minimax Distance; Spectral Clustering; MidPoint Heuristic

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 are provided to illustrate its effectiveness.

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 be immediately updated when a tree edge is deleted. We propose algorithms to maintain the replacement edge for each tree edge by sharing the computation cost in the updating process. Our performance studies on large datasets demonstrate considerable improvements over state-of-the-art solutions.

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 reduces to a k -Hamiltonian path problem. Application domains where DC k MST can be adapted or directly utilized include backbone network structures in telecommunications, facility location, and transportation networks, to name a few. It is easy to see from the literature that the DC k MST problem has not been studied in depth so far. Thus, our main contributions in this paper can be highlighted as follows. We propose three mixed-integer linear programming (MILP) models for the DC k MST problem and derive for each one an equivalent counterpart by using the handshaking lemma. Then, we further propose ant colony optimization (ACO) and variable neighborhood search (VNS) algorithms. Each proposed ACO and VNS method is also compared with another variant of it which is obtained while embedding a Q-learning strategy. We also propose a pure Q-learning algorithm that is competitive with the ACO ones. Finally, we conduct substantial numerical experiments using benchmark input graph instances from TSPLIB and randomly generated ones with uniform and Euclidean distance costs with up to 400 nodes. Our numerical results indicate that the proposed models and algorithms allow obtaining optimal and near-optimal solutions, respectively. Moreover, we report better solutions than CPLEX for the large-size instances. Ultimately, the empirical evidence shows that the proposed Q-learning strategies can bring considerable improvements.

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. Pengambilan data dilakukan di kantor PDAM Tirta Muaro Jambi, Provinsi Jambi. Dari data yang diperoleh dapat disusun gambar jaringan dalam bentuk graf terhubung dan tak berarah serta memiliki bobot. Dari gambar jaringan tersebut selanjutnya dilakukan pencarian Minimum Spanning Tree. Pada penelitian ini, dapat diketahui bahwa pencarian Minimum Spanning Tree menggunakan algoritma prim baik secara manual maupun dengan bantuan software TORA, menunjukkan pemilihan sisi pada iterasi yang sama dan menghasilkan struktur MST dengan jumlah bobot yang sama juga yaitu sebesar 5.876 meter. Dibandingkan dengan graf awal yang berbobot 7.898 meter, maka hasil dari Minimum Spanning Tree menunjukkan selisih bobot pipa yang cukup signifikan yaitu sebesar 2.022 meter.

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-th lowest spanning tree. The lowest spanning tree meets some additional constraints that may be found. We will discuss Murty's algorithm in this paper, which can find all solutions to assignment problem of increasing cost, and also discuss complexities of time and space

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. cities show that forecasts of the temperature–humidity index are the most reliable of those considered, followed by mean sea level pressure, 2-m temperature, and 10-m wind speed forecasts. MST RHs of a Southwest city cluster illustrate that 2-m temperature forecasts are the most reliable weather component in this region, followed by mean sea level pressure, 10-m wind speed, and the temperature–humidity index. Forecast reliabilities of the Southwest city cluster are generally less reliable than those of the Northeast cluster.

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 Minum Tirta Mayang di Perumahan Sunderland menggunakan Algoritma Reverse-Delete. Graf dari jaringan pipa tersier PERUMDA Air Minum Tirta Mayang di Perumahan Sunderland mempunyai cukup banyak sisi dan titik sehingga pencarian Minimum Spanning Tree (MST) cukup efektif dilakukan dengan menggunakan Algoritma Reverse-Delete. Algoritma Reverse-Delete sangat tepat untuk digunakan pada graf dengan jumlah sisi dan titik yang banyak karena pencarian Minimum Spanning Tree (MST) dengan Algoritma Reverse-Delete dilakukan berdasarkan pada urutan bobot sisi, bukan berdasarkan pada titik. Berdasarkan hasil pencarian Minimum Spanning Tree (MST) dengan menerapkan Algoritma Reverse-Delete, maka diperoleh panjang total jaringan pipa tersier PERUMDA Air Minum Tirta Mayang di Perumahan Sunderland adalah 3.968 meter dengan 70 titik dan 69 sisi dari graf awal dengan panjang jaringan 4.493 meter dengan 70 titik dan 74 sisi. Dengan demikian, terdapat 5 sisi yang dihapus sehingga menyebabkan adanya penghematan pipa pendistribusian air sepanjang 525 meter pipa tersier.

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "MST (minimum spanning tree)"

1

Chu, Ding. "BSP Implementation of Boruvka's Minimum Spanning Tree Algorithm." Kent State University / OhioLINK, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=kent1424483867.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Zhang, Yuan. "MST Based Ab Initio Assembler of Expressed Sequence Tags." Miami University / OhioLINK, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=miami1273245641.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Oshiro, Marcio Takashi Iura. "k-árvores de custo mínimo." Universidade de São Paulo, 2010. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-28052012-091652/.

Full text

Abstract:

Esta dissertação trata do problema da k-árvore de custo mínimo (kMST): dados um grafo conexo G, um custo não-negativo c_e para cada aresta e e um número inteiro positivo k, encontrar uma árvore com k vértices que tenha custo mínimo. O kMST é um problema NP-difícil e portanto não se conhece um algoritmo polinomial para resolvê-lo. Nesta dissertação discutimos alguns casos em que é possível resolver o problema em tempo polinomial. Também são estudados algoritmos de aproximação para o kMST. Entre os algoritmos de aproximação estudados, apresentamos a 2-aproximação desenvolvida por Naveen Garg, que atualmente é o algoritmo com melhor fator de aproximação.<br>This dissertation studies the minimum cost k-tree problem (kMST): given a connected graph G, a nonnegative cost function c_e for each edge e and a positive integer k, find a minimum cost tree with k vertices. The kMST is an NP-hard problem, which implies that it is not known a polynomial algorithm to solve it. In this dissertation we discuss some cases that can be solved in polynomial time. We also study approximation algorithms for the kMST. Among the approximation algorithms we present the 2-approximation developed by Naveen Garg, which is currently the algorithm with the best approximation factor.

APA, Harvard, Vancouver, ISO, and other styles

4

Tomaz, Felipe Rodrigues de Menezes. "Estudo de utilização de uma minimum spanning tree de correlações como seletora de ações em uma estratégia de cointegração no mercado brasileiro." reponame:Repositório Institucional do FGV, 2017. http://hdl.handle.net/10438/18032.

Full text

Abstract:

Submitted by Felipe Rodrigues de Menezes Tomaz (felipetomaz@gmail.com) on 2017-03-08T18:07:35Z No. of bitstreams: 1 Dissertação - Final.pdf: 1323190 bytes, checksum: c28bd29047e066ff34bb9203c46e9fec (MD5)<br>Rejected by Renata de Souza Nascimento (renata.souza@fgv.br), reason: Felipe, boa noite Por gentileza, realizar as seguintes alterações para que possamos aceitar seu trabalho: Retirar a acentuação do nome Getúlio Centralizar os títulos: Dedicatória, Resumo e Abstract. O título está diferente com o que consta em Ata e nenhuma solicitação do orientador. Neste caso, iremos entrar em contato para que o mesmo confirme a alteração. Em seguida, deverá submeter o arquivo novamente. Att on 2017-03-08T23:14:39Z (GMT)<br>Submitted by Felipe Rodrigues de Menezes Tomaz (felipetomaz@gmail.com) on 2017-03-09T12:57:43Z No. of bitstreams: 1 Dissertação - Final.pdf: 1323164 bytes, checksum: 26add34e2f577cfcec02f52da04b7845 (MD5)<br>Rejected by Renata de Souza Nascimento (renata.souza@fgv.br), reason: Felipe, boa tarde Em contato com o prof. Ricardo Rochman, o mesmo confirma que não solicitou e não autoriza a mudança no título do trabalho. Deverá retornar ao título que consta em Ata e protocolo inicial: ESTUDO DE UTILIZAÇÃO DE UMA MINIMUM SPANNING TREE DE CORRELAÇÕES COMO SELETORA DE AÇÕES EM UMA ESTRATÉGIA DE COINTEGRAÇÃO NO MERCADO DE BRASILEIRO Att. on 2017-03-09T16:15:49Z (GMT)<br>Submitted by Felipe Rodrigues de Menezes Tomaz (felipetomaz@gmail.com) on 2017-03-09T19:35:28Z No. of bitstreams: 1 Dissertação - Final.pdf: 1322284 bytes, checksum: 9ec2cbcae5a0293ac6a12c5a9ae85ebf (MD5)<br>Approved for entry into archive by Renata de Souza Nascimento (renata.souza@fgv.br) on 2017-03-09T19:40:49Z (GMT) No. of bitstreams: 1 Dissertação - Final.pdf: 1322284 bytes, checksum: 9ec2cbcae5a0293ac6a12c5a9ae85ebf (MD5)<br>Made available in DSpace on 2017-03-10T13:02:47Z (GMT). No. of bitstreams: 1 Dissertação - Final.pdf: 1322284 bytes, checksum: 9ec2cbcae5a0293ac6a12c5a9ae85ebf (MD5) Previous issue date: 2017-02-10<br>This work aimed to evaluate the possibility of using a miminum spanning tree (MST) of correlation between assets as a selection tool in a pairs trading strategy based on cointegration. From a selection of Bovespa exchange index assets, cointegration tests were performed between pairs of assets and, subsequently, starting from positive results, backtestings were executed. After that, the backtestings were filtered by information included in an MST. For a given period, when a cointegration was found between a pair of assets, a MST was developed and it was analyzed if there was a direct link between those assets in the MST’s structure. Otherwise, the backtesting result from the cointegration would be disregarded. By comparing the total set of results with the subset of results that took into account the MST constraint, it was evaluated the impact of the use of the MST, as an asset selector, on the result of the pairs trading strategy.<br>Essa dissertação teve como objetivo avaliar a possibilidade de utilização de uma miminum spanning tree (MST) de correlação entre ativos como instrumento de seleção em uma estratégia de pairs trading que teve como base a cointegração. A partir de uma seleção de ativos do índice Bovespa, foram feitos testes de cointegração entre pares de ativos e, posteriormente, partindo de resultados positivos, foram executados backtestings que foram filtrados por informações provenientes de uma MST. Para determinado período, ao se encontrar uma cointegração entre um par dos ativos considerados, uma MST foi desenvolvida e analisou-se a existência de um link direto entre o par de ativos na estrutura da MST. Caso contrário, o resultado do backtesting proveniente desta cointegração foi desconsiderado. Fazendo-se a comparação do conjunto total de resultados com o subconjunto de resultados que levam em consideração a restrição da MST, avaliou-se o impacto da utilização da MST, como seletora de ativos, no resultado da estratégia de pairs trading.

APA, Harvard, Vancouver, ISO, and other styles

5

Che, Chan Hou. "Generalized minimum spanning tree problem /." View abstract or full-text, 2006. http://library.ust.hk/cgi/db/thesis.pl?IELM%202006%20CHE.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Viana, Luiz Alberto do Carmo. "Dependency constrained minimum spanning tree." Universidade Federal do CearÃ, 2016. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=17302.

Full text

Abstract:

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico<br>Introduzimos o problema de Ãrvore Geradora com DependÃncias MÃnima, AGDM(G,D,w), definido sobre um grafo G(V,E) e um digrafo D(E,A), cujos vÃrtices sÃo as arestas de G e cujos arcos definem dependÃncias entre tais arestas. O problema consiste em encontrar, dentre as Ãrvores geradoras do grafo G(V,E) que satisfaÃam as restriÃÃes de dependÃncia impostas pelo digrafo de entrada D(E,A), uma que tenha custo mÃnimo, segundo a ponderaÃÃo w das arestas de G. As restriÃÃes de dependÃncia exigem que uma aresta e de G sÃ pode fazer parte de uma soluÃÃo se for uma fonte em D ou se fizer parte da soluÃÃo alguma outra aresta Ã tal que o arco (e′, e) esteja em D. Provamos que decidir se hÃ soluÃÃo viÃvel para AGDM(G,D,w) Ã um problema NP-completo, mesmo quando G Ã um cacto cordal e D Ã a uniÃo de arborescÃncias de altura no mÃximo 2. Sua NP-completude tambÃm Ã mostrada ainda que G seja bipartido, as restriÃÃes de dependÃncia ocorram apenas entre arestas adjacentes de G e formem arborescÃncias de altura no mÃximo 2. Resultados idÃnticos sÃo obtidos para as variantes do problema onde, nas restriÃÃes de dependÃncia, substitui-se o requisito âalgumaâ por âexatamente umaâ ou âtodaâ. Para resolver o problema, apresentamos algumas formulaÃÃes de programaÃÃo inteira e desigualdades vÃlidas. Propomos uma estratÃgia para reduzir a dimensÃo do problema, excluindo arestas de G com base na estrutura de D. Avaliamos os modelos e algoritmos propostos usando instÃncias geradas aleatoriamente. Resultados computacionais sÃo reportados.<br>We introduce the Dependency Constrained Minimum Spanning Tree Problem, DCMST(G,D,w), defined over a graph G(V,E) and a digraph D(E,A), whose vertices are the edges of G and whose arcs describe dependency relations between these edges. Such problem consists of finding, among the spanning trees of G(V,E) satisfying the dependency constraints imposed by D(E,A), that one whose cost is minimum, according to a edgeweight function w. The dependency constraints impose that an edge e of G can be part of a solution either if it is a source in D or if some other edge e′, such that the arc (e′, e) is in D, is part of it as well. We prove that deciding whether there is a feasible solution to DCMST(G,D,w) is an NP-complete problem, even if G is a chordal cactus and D is a union of arborescences of height at most 2. NP-completeness also applies if G is bipartite, the dependency constraints occur only between adjacent edges of G and their related arcs describe arborescences whose height is at most 2. The same results are obtained for the problem variants which demand that, instead of âsomeâ, âexactly oneâor âallâdependencies be part of a solution. To solve the problem, we introduce some integer programming formulations and some valid inequalities. We propose a strategy to reduce the problem dimension by excluding some edges of G according to the structure of D. We evaluate the introduced models and algorithms using randomly generated instances. Computational results are reported.

APA, Harvard, Vancouver, ISO, and other styles

7

Choudhury, Sabyasachy. "Hierarchical Data Structures for Pattern Recognition." Thesis, Indian Institute of Science, 1987. https://etd.iisc.ac.in/handle/2005/74.

Full text

Abstract:

Pattern recognition is an important area with potential applications in computer vision, Speech understanding, knowledge engineering, bio-medical data classification, earth sciences, life sciences, economics, psychology, linguistics, etc. Clustering is an unsupervised classification process corning under the area of pattern recognition. There are two types of clustering approaches: 1) Non-hierarchical methods 2) Hierarchical methods. Non-hierarchical algorithms are iterative in nature and. perform well in the context of isotropic clusters. Time-complexity of these algorithms is order of (0 (n) ) and above, Hierarchical agglomerative algorithms, on the other hand, are effective when clusters are non-isotropic. The single linkage method of hierarchical category produces a dendrogram which corresponds to the minimal spanning tree, conventional approaches are time consuming requiring O (n2 ) computational time. In this thesis we propose an intelligent partitioning scheme for generating the minimal spanning tree in the co-ordinate space. This is computationally elegant as it avoids the computation of similarity between many pairs of samples me minimal spanning tree generated can be used to produce C disjoint clusters by breaking the (C-1) longest edges in the tree. A systolic architecture has been proposed to increase the speed of the algorithm further. Simulation study has been conducted and the corresponding results are reported. The simulation package has been developed on DEC-1090 in Pascal. It is observed based on the simulation study that the parallel implementation reduces the time enormously. The number of processors required for the parallel implementation is a constant making the approach more attractive. Texture analysis and synthesis has been extensively studied in the context of computer vision, Two important approaches which have been studied extensively by researchers earlier are statistical and structural approaches, Texture is understood to be a periodic pattern with primitive sub patterns repeating in a particular fashion. This has been used to characterize texture with the help of the hierarchical data structure, tree. It is convenient to use a tree data structure as, along with the operations like merging, splitting, deleting a node, adding a node, etc, .it would be useful to handle a periodic pattern. Various functions like angular second moment, correlation etc, which are used to characterize texture have been translated into the new language of hierarchical data structure.

APA, Harvard, Vancouver, ISO, and other styles

8

Choudhury, Sabyasachy. "Hierarchical Data Structures for Pattern Recognition." Thesis, Indian Institute of Science, 1987. http://hdl.handle.net/2005/74.

Full text

Abstract:

Pattern recognition is an important area with potential applications in computer vision, Speech understanding, knowledge engineering, bio-medical data classification, earth sciences, life sciences, economics, psychology, linguistics, etc. Clustering is an unsupervised classification process corning under the area of pattern recognition. There are two types of clustering approaches: 1) Non-hierarchical methods 2) Hierarchical methods. Non-hierarchical algorithms are iterative in nature and. perform well in the context of isotropic clusters. Time-complexity of these algorithms is order of (0 (n) ) and above, Hierarchical agglomerative algorithms, on the other hand, are effective when clusters are non-isotropic. The single linkage method of hierarchical category produces a dendrogram which corresponds to the minimal spanning tree, conventional approaches are time consuming requiring O (n2 ) computational time. In this thesis we propose an intelligent partitioning scheme for generating the minimal spanning tree in the co-ordinate space. This is computationally elegant as it avoids the computation of similarity between many pairs of samples me minimal spanning tree generated can be used to produce C disjoint clusters by breaking the (C-1) longest edges in the tree. A systolic architecture has been proposed to increase the speed of the algorithm further. Simulation study has been conducted and the corresponding results are reported. The simulation package has been developed on DEC-1090 in Pascal. It is observed based on the simulation study that the parallel implementation reduces the time enormously. The number of processors required for the parallel implementation is a constant making the approach more attractive. Texture analysis and synthesis has been extensively studied in the context of computer vision, Two important approaches which have been studied extensively by researchers earlier are statistical and structural approaches, Texture is understood to be a periodic pattern with primitive sub patterns repeating in a particular fashion. This has been used to characterize texture with the help of the hierarchical data structure, tree. It is convenient to use a tree data structure as, along with the operations like merging, splitting, deleting a node, adding a node, etc, .it would be useful to handle a periodic pattern. Various functions like angular second moment, correlation etc, which are used to characterize texture have been translated into the new language of hierarchical data structure.

APA, Harvard, Vancouver, ISO, and other styles

9

Ruiz, y. Ruiz Héctor Efraín. "The capacitated minimum spanning tree problem." Doctoral thesis, Universitat Politècnica de Catalunya, 2013. http://hdl.handle.net/10803/129631.

Full text

Abstract:

In this thesis we focus on the Capacitated Minimum Spanning Tree (CMST), an extension of the minimum spanning tree (MST) which considers a central or root vertex which receives and sends commodities (information, goods, etc) to a group of terminals. Such commodities flow through links which have capacities that limit the total flow they can accommodate. These capacity constraints over the links result of interest because in many applications the capacity limits are inherent. We find the applications of the CMST in the same areas as the applications of the MST; telecommunications network design, facility location planning, and vehicle routing. The CMST arises in telecommunications networks design when the presence of a central server is compulsory and the flow of information is limited by the capacity of either the server or the connection lines. Its study also results specially interesting in the context of the vehicle routing problem, due to the utility that spanning trees can have in constructive methods. By the simple fact of adding capacity constraints to the MST problem we move from a polynomially solvable problem to a non-polynomial one. In the first chapter we describe and define the problem, introduce some notation, and present a review of the existing literature. In such review we include formulations and exact methods as well as the most relevant heuristic approaches. In the second chapter two basic formulations and the most used valid inequalities are presented. In the third chapter we present two new formulations for the CMST which are based on the identification of subroots (vertices directly connected to the root). One way of characterizing CMST solutions is by identifying the subroots and the vertices assigned to them. Both formulations use binary decision variables y to identify the subroots. Additional decision variables x are used to represent the elements (arcs) of the tree. In the second formulation the set of x variables is extended to indicate the depth of the arcs in the tree. For each formulation we present families of valid inequalities and address the separation problem in each case. Also a solution algorithm is proposed. In the fourth chapter we present a biased random-key genetic algorithm (BRKGA) for the CMST. BRKGA is a population-based metaheuristic, that has been used for combinatorial optimization. Decoders, solution representation and exploring strategies are presented and discussed. A final algorithm to obtain upper bounds for the CMST is proposed. Numerical results for the BRKGA and two cutting plane algorithms based on the new formulations are presented in the fifth chapter . The above mentioned results are discussed and analyzed in this same chapter. The conclusion of this thesis are presented in the last chapter, in which we include the opportunity areas suitable for future research.<br>En esta tesis nos enfocamos en el problema del Árbol de Expansión Capacitado de Coste Mínimo (CMST, por sus siglas en inglés), que es una extensión del problema del árbol de expansión de coste mínimo (MST, por sus siglas en inglés). El CMST considera un vértice raíz que funciona como servidor central y que envía y recibe bienes (información, objetos, etc) a un conjunto de vértices llamados terminales. Los bienes solo pueden fluir entre el servidor y las terminales a través de enlaces cuya capacidad es limitada. Dichas restricciones sobre los enlaces dan relevancia al problema, ya que existen muchas aplicaciones en que las restricciones de capacidad son de vital importancia. Dentro de las áreas de aplicación del CMST más importantes se encuentran las relacionadas con el diseño de redes de telecomunicación, el diseño de rutas de vehículos y problemas de localización. Dentro del diseño de redes de telecomunicación, el CMST está presente cuando se considera un servidor central, cuya capacidad de transmisión y envío está limitada por las características de los puertos del servidor o de las líneas de transmisión. Dentro del diseño de rutas de vehículos el CMST resulta relevante debido a la influencia que pueden tener los árboles en el proceso de construcción de soluciones. Por el simple de añadir las restricciones de capacidad, el problema pasa de resolverse de manera exacta en tiempo polinomial usando un algoritmo voraz, a un problema que es muy difícil de resolver de manera exacta. En el primer capítulo se describe y define el problema, se introduce notación y se presenta una revisión bibliográfica de la literatura existente. En dicha revisión bibliográfica se incluyen formulaciones, métodos exactos y los métodos heurísticos utilizados más importantes. En el siguiente capítulo se muestran dos formulaciones binarias existentes, así como las desigualdades válidas más usadas para resolver el CMST. Para cada una de las formulaciones propuestas, se describe un algoritmo de planos de corte. Dos nuevas formulaciones para el CMST se presentan en el tercer capítulo. Dichas formulaciones estás basadas en la identificación de un tipo de vértices especiales llamados subraíces. Los subraíces son aquellos vértices que se encuentran directamente conectados al raíz. Un forma de caracterizar las soluciones del CMST es a través de identificar los nodos subraíces y los nodos dependientes a ellos. Ambas formulaciones utilizan variables para identificar los subraices y variables adicionales para identificar los arcos que forman parte del árbol. Adicionalmente, las variables en la segunda formulación ayudan a identificar la profundidad con respecto al raíz a la que se encuentran dichos arcos. Para cada formulación se presentan desigualdades válidas y se plantean procedimientos para resolver el problema de su separación. En el cuarto capítulo se presenta un algoritmo genético llamado BRKGA para resolver el CMST. El BRKGA está basado en el uso de poblaciones generadas por secuencias de números aleatorios, que posteriormente evolucionan. Diferentes decodificadores, un método de búsqueda local, espacios de búsqueda y estrategias de exploración son presentados y analizados. El capítulo termina presentando un algoritmo final que permite la obtención de cotas superiores para el CMST. Los resultados computacionales para el BRKGA y los dos algoritmos de planos de corte basados en las formulaciones propuestas se muestran en el quinto capítulo. Dichos resultados son analizados y discutidos en dicho capítulo. La tesis termina presentando las conclusiones derivadas del desarrollo del trabajo de investigación, así como las áreas de oportunidad sobre las que es posible realizar futuras investigaciones.

APA, Harvard, Vancouver, ISO, and other styles

10

Abdalla, Ayman Mahmoud. "Computing a diameter-constrained minimum spanning tree." Doctoral diss., University of Central Florida, 2001. http://digital.library.ucf.edu/cdm/ref/collection/RTD/id/5567.

Full text

Abstract:

University of Central Florida College of Engineering Thesis<br>In numerous practical applications, it is necessary to find the smallest possible tree with a bounded diameter. A diameter-constrained minimum spanning tree (DCMST) of a given undirected, edge-weighted graph, G, is the smallest-weight spanning tree of all spanning trees of G which contain no path with more than k edges, where k is a given positive integer. The problem of finding a DCMST is NP-complete for all values of k; 4 <= k <= (n - 2), except when all edge-weights are identical. A DCMST is essential for the efficiency of various distributed mutual exclusion algorithms, where it can minimize the number of messages communicated among processors per critical section. It is also useful in linear lightwave networks, where it can minimize interference in the network by limiting the traffic in the network lines. Another practical application requiring a DCMST arises in data compression, where some algorithms compress a file utilizing a data-structure, and decompress a path in the tree to access a record A DCMST helps such algorithm to be fast without sacrificing a lot of storage storage space .<br>Ph.D.<br>School of Electrical Engineering and Computer Science<br>Engineering and Computer Science<br>Electrical Engineering and Computer Science<br>172 p.

APA, Harvard, Vancouver, ISO, and other styles

More sources

Books on the topic "MST (minimum spanning tree)"

1

Indian Institute of Management, Ahmedabad., ed. Solving medium to large sized euclidean generalized minimum spanning tree problems. Indian Institute of Management, 2003.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

2

Bertsimas, Dimitris. The probabilistic minimum spanning tree problem: Part I--complexity and combinatorial properties. Sloan School of Management, Massachusetts Institute of Technology, 1988.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

3

Indian Institute of Management, Ahemdabad., ed. A probabilistic tabu search algorithm for the generalized minimum spanning tree problem. Indian Institute of Management, 2003.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

4

Faloutsos, Michalis. Corrections, improvements, simulations and optiMSTic algorithms for the distributed minimum spanning tree problem. University of Toronto, Dept. of Computer Science, 1995.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

5

Faloutsos, Michalis. Corrections, improvements, simulations and optimistic algorithms for the distributed minimum spanning tree problem. National Library of Canada, 1994.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

6

Bertsimas, Dimitris, and Sloan School of Management. Probabilistic Minimum Spanning Tree Problem: Part I--Complexity and Combinatorial Properties. Creative Media Partners, LLC, 2018.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

7

Probabilistic Minimum Spanning Tree Problem: Part I--Complexity and Combinatorial Properties. Creative Media Partners, LLC, 2023.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

8

Gómez Manzanares, Juan Felipe, Álvaro Pachón de la Cruz, Sebastián Felipe Landínez García, Andrés Navarro Cadavid, Loaiza César, and Gabriel Tamura Morimitsu. Aprovisionamiento ágil – Clasificación de malware – Optimización Giraph. Universidad Icesi, 2020. http://dx.doi.org/10.18046/eui/bm.7.2020.

Full text

Abstract:

Esta edición de Bitácoras de la Maestría es una buena muestra de la diversidad de problemas que se pueden resolver con el aporte de la informática. En el primer capítulo se trata tangencialmente un tema sobre el que hay mucha discusión, la industria 4.0, la denominada cuarta revolución industrial, con énfasis en “adaptación”. El tema del segundo capítulo es la seguridad de los dispositivos móviles que funcionan con un sistema operativo Android. El tercer capítulo presenta una solución para un problema de optimización complejo, el Rooted Distance-Constrained Minimum Spanning Tree (RDCMST), muy útil en temas con el diseño de redes de telecomunicaciones.

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "MST (minimum spanning tree)"

1

Srinivas, Rayudu, T. Rama Reddy, R. V. S. Lalitha, and Shaik Vahida. "A Novel Approach to Find Minimum Cost Spanning Tree (MST) of a Graph." In Lecture Notes in Networks and Systems. Springer Singapore, 2021. http://dx.doi.org/10.1007/978-981-16-0980-0_9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Obu-Cann, K., K. Fujimura, H. Tokutaka, M. Ohkita, M. Inui, and S. Yamada. "Exploring power transformer database using Self-Organising Maps (SOM) and Minimal Spanning Tree (MST)." In Advances in Self-Organising Maps. Springer London, 2001. http://dx.doi.org/10.1007/978-1-4471-0715-6_19.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Choi, Heung-Kook, Ewert Bengtsson, Torsten Jarkrans, et al. "Minimum spanning trees (MST) as a tool for describing tissue architecture when grading bladder carcinoma." In Image Analysis and Processing. Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/3-540-60298-4_322.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Ling, Jin, and Nadezda Sorokina. "Visualizing and Comparing Online Travel Reviews of the Great Walls: A Data Mining Approach." In Information and Communication Technologies in Tourism 2022. Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-94751-4_39.

Full text

Abstract:

AbstractThis research employs two samples of heritage sites of the Great Wall of China (Ba daling Great Wall and Mu tianyu Great Wall) and their 21000 reviews on TripAdvisor to visualize and induce feature-related comparisons. Word2vec and D3.js are applied for statistical computing and graphing Minimal Spanning Tree (MST) and ThemeRiver. The applications of MST and ThemeRiver are used to delineate outstanding features and clearer feature relationships. In terms of methodology, we applied an innovative research route to combine MST with ThemeRiver to visualize travellers’ online comments. At the same time, the visual results obtained are combined with qualitative analysis to generate valuable, intuitive summaries that can be used for reference in future research. Practically, the results disclose that although both sites are highly enjoyed by tourists, they are significantly different in terms of service, infrastructure and scenery. This article has implications for policymakers and practitioners with regard to making use of online reviews to gather authentic visitor comments on the Great Wall.

APA, Harvard, Vancouver, ISO, and other styles

5

Bazgan, Cristina, Sonia Toubaline, and Daniel Vanderpooten. "Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem." In Combinatorial Optimization and Applications. Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22616-8_11.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Fraer, Ranan. "Minimum Spanning Tree." In Program Development by Refinement. Springer London, 1999. http://dx.doi.org/10.1007/978-1-4471-0585-5_3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Ramachandran, Vijaya. "Randomized Minimum Spanning Tree." In Encyclopedia of Algorithms. Springer New York, 2016. http://dx.doi.org/10.1007/978-1-4939-2864-4_325.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Ramachandran, Vijaya. "Randomized Minimum Spanning Tree." In Encyclopedia of Algorithms. Springer US, 2015. http://dx.doi.org/10.1007/978-3-642-27848-8_325-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Ramachandran, Vijaya. "Randomized Minimum Spanning Tree." In Encyclopedia of Algorithms. Springer US, 2008. http://dx.doi.org/10.1007/978-0-387-30162-4_325.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Shekhar, Shashi, and Hui Xiong. "Generalized Minimum Spanning Tree." In Encyclopedia of GIS. Springer US, 2008. http://dx.doi.org/10.1007/978-0-387-35973-1_451.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "MST (minimum spanning tree)"

1

Ghosh, Pulak, and Gaurav Mishra. "kMiST: A KD-Tree Based Fast Minimum Spanning Tree Algorithm." In 2024 15th International Conference on Computing Communication and Networking Technologies (ICCCNT). IEEE, 2024. http://dx.doi.org/10.1109/icccnt61001.2024.10724535.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Satyanarayana, D., Gopal Rathinam, Abdullah Said Al Kalbani, Nadir Kamal Salih Idries, and Alaya Al Azzani. "A Robot Navigation Method Using Restricted Minimum Spanning Tree." In 2024 10th International Conference on Electrical Engineering, Control and Robotics (EECR). IEEE, 2024. http://dx.doi.org/10.1109/eecr60807.2024.10607176.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Kponyo, Jerry John, Yujun Kuang, Enzhan Zhang, and Kamenyi Domenic. "VANET Cluster-on-Demand Minimum Spanning Tree (MST) Prim clustering algorithm." In 2013 International Conference on Computational Problem-solving (ICCP). IEEE, 2013. http://dx.doi.org/10.1109/iccps.2013.6893585.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Vo, Quang Hieu, Linh-Tam Tran, Sung-Ho Bae, Lok-Won Kim, and Choong Seon Hong. "MST-compression: Compressing and Accelerating Binary Neural Networks with Minimum Spanning Tree." In 2023 IEEE/CVF International Conference on Computer Vision (ICCV). IEEE, 2023. http://dx.doi.org/10.1109/iccv51070.2023.00560.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Pir Mohammadiani, Rojiar, Maryam Mozaffari, and Soma Solaiman Zadeh. "Unsupervised Feature Selection Method based on Structural Particularity of Minimum Spanning Tree." In 4th International Conference on Communication Engineering and Computer Science (CIC-COCOS’2022). Cihan University, 2022. http://dx.doi.org/10.24086/cocos2022/paper.828.

Full text

Abstract:

Unsupervised Feature Selection (UFS) methods try to extract features that can well keep the intrinsic structure of data. To make full use of such information in this paper we use one of the simplest graph sparsification strategies MST (Minimum Spanning Tree) for the task of UFS. A novel graph structural information method is proposed for unsupervised feature selection, we simplify and preserve correlation between features via MST through a structure that simultaneously captures the local and global structure of data, and then use graph structural information directly to achieve the subset representative features with minimum redundancy and more discriminative power. To show the effectiveness of our method, some of the most representative and referenced UFS methods are used for conducting experiments on some benchmark datasets. Experimental results verify that the proposed feature subset selection algorithm is effective, more specifically at the running time.

APA, Harvard, Vancouver, ISO, and other styles

6

Wang, Ruikun, Jiawei Zhang, Memedhe Ibrahimi, et al. "Network for AI: Communication-Efficient Federated Learning with MST-based Scheduling and Multi-Aggregation over Optical Networks." In Optical Fiber Communication Conference. Optica Publishing Group, 2024. http://dx.doi.org/10.1364/ofc.2024.tu3b.3.

Full text

Abstract:

We propose a Minimum-Spanning-Tree-based scheduling and Multi-aggregation framework (MST-M) for communication-efficient Federated Learning. Simulation results show that MST-M saves over 10% in communication costs compared to existing heuristics.

APA, Harvard, Vancouver, ISO, and other styles

7

Mahamood, Fatin Nur Amirah, Hafizah Bahaludin, and Mimi Hafizah Abdullah. "Network analysis of shariah-compliant stocks on Bursa Malaysia by using minimum spanning tree (MST)." In THE 4TH INNOVATION AND ANALYTICS CONFERENCE & EXHIBITION (IACE 2019). AIP Publishing, 2019. http://dx.doi.org/10.1063/1.5121093.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Nehra, Priyanka, and A. Nagaraju. "Fault Tolerance using Quadratic-Minimum Spanning Tree (Q-MST) with Secure Data Aggregation in Wireless Sensor Networks." In 2017 14th IEEE India Council International Conference (INDICON). IEEE, 2017. http://dx.doi.org/10.1109/indicon.2017.8488039.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Saha, Baidya Nath, Nilanjan Ray, Sara McArdle, and Klaus Ley. "A two-stage minimum spanning tree (MST) based clustering algorithm for 2D deformable registration of time sequenced images." In 2017 IEEE International Conference on Image Processing (ICIP). IEEE, 2017. http://dx.doi.org/10.1109/icip.2017.8296526.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Bejanyan, V., and H. Astsatryan. "VM BASED EVALUATION OF THE SCALABLE PARALLEL MINIMUM SPANNING TREE ALGORITHM FOR PGAS MODEL." In 9th International Conference "Distributed Computing and Grid Technologies in Science and Education". Crossref, 2021. http://dx.doi.org/10.54546/mlit.2021.75.94.001.

Full text

Abstract:

The minimum spanning tree problem has influential importance in computer science, networkanalysis, and engineering. However, the sequential algorithms become unable to process the givenproblem as the volume of the data representing graph instances overgrowing. Instead, the highperformance computational resources pursue to simulate large-scale graph instances in a distributedmanner. Generally, the standard shared or distributed memory models like OpenMP and MessagePassing Interface are applied to address the parallelization. Nevertheless, as an emerging alternative,the Partitioned Global Address Space model communicates in the form of asynchronous remoteprocedure calls to access distributed-shared memory, positively affecting the performance usingoverlapping communications and locality-aware structures. The paper presents a modification of theKruskal algorithm for MST problems based on performance and energy-efficiency evaluation relyingon emerging technologies. The algorithm evaluation shows great scalability within the server up to 16vCPU and between the physical servers coupled with a connected weighted graph using differentvertices, edges, and densities.

APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "MST (minimum spanning tree)"

1

Welch, Jennifer L., Leslie Lamport, and Nancy Lynch. A Lattice-Structured Proof Technique Applied to a Minimum Spanning Tree Algorithm. Defense Technical Information Center, 1988. http://dx.doi.org/10.21236/ada198312.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Striuk, Andrii, Olena Rybalchenko, and Svitlana Bilashenko. Development and Using of a Virtual Laboratory to Study the Graph Algorithms for Bachelors of Software Engineering. [б. в.], 2020. http://dx.doi.org/10.31812/123456789/4462.

Full text

Abstract:

The paper presents an analysis of the importance of studying graph algorithms, the reasons for the need to implement this project and its subsequent use. The existing analogues analysis is carried out, due to which a list of advantages and disadvantages is formed and taken into account in developing the virtual laboratory. A web application is created that clearly illustrates the work of graph algorithms, such as Depth-First Search, Dijkstra’s Shortest Path, Floyd- Warshall, Kruskal Minimum Cost Spanning Tree Algorithm. A simple and user- friendly interface is developed and it is supported by all popular browsers. The software product is provided with user registration and authorization functions, chat communication, personal cabinet editing and viewing the statistics on web- application use. An additional condition is taken into account at the design stage, namely the flexibility of the architecture, which envisaged the possibility of easy expansion of an existing functionality. Virtual laboratory is used at Kryvyi Rih National University to training students of specialty 121 Software Engineering in the disciplines “Algorithms and Data Structures” and “Discrete Structures”.

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!