Minimum-weight spanning tree algorithms - A survey and empirical study

Date

2001-07-01

Author

Bazlamaçcı, Cüneyt Fehmi

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

141
views

0
downloads

The minimum-weight spanning tree problem is one of the most typical and well-known problems of combinatorial optimisation. Efficient solution techniques had been known for many years. However, in the last two decades asymptotically faster algorithms have been invented. Each new algorithm brought the time bound one step closer to linearity and finally Karger, Klein and Tarjan proposed the only known expected linear-time method. Modern algorithms make use of more advanced data structures and appear to be more complicated to implement. Most authors and practitioners refer to these but still use the classical ones, which are considerably simpler but asymptotically slower. The paper first presents a survey of the classical methods and the more recent algorithmic developments. Modern algorithms are then compared with the classical ones and their relative performance is evaluated through extensive empirical tests, using reasonably large-size problem instances. Randomly generated problem instances used in the tests range from small networks having 512 nodes and 1024 edges to quite large ones with 16384 nodes and 524288 edges. The purpose of the comparative study is to investigate the conjecture that modern algorithms are also easy to apply and have constants of proportionality small enough to make them competitive in practice with the older ones.

Subject Keywords

Performance evaluation, Linear-time algorithms, Minimum spanning tree, Graph algorithms, Network optimisation

URI

https://hdl.handle.net/11511/54393

Journal

COMPUTERS & OPERATIONS RESEARCH

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

Hybrid heuristic algorithms for the multi objective load balancing of 2D bin packing problems Muhammet, Beyaz; Dökeroğlu, Tansel; Coşar, Ahmet (null; 2015-09-23) 2D Bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem. Multiobjective versions of this well-known industrial engineering problem can occur frequently in real world application. Recently, Hybrid Evolutionary Algorithms have appear as a new area of research with their ability to combine alternative heuristics and local search mechanisms together for higher quality solutions. In this study, we propose a set of novel multiobjective hybrid genetic and memetic algorithms that make use of...
PARALLEL MULTILEVEL FAST MULTIPOLE ALGORITHM FOR COMPLEX PLASMONIC METAMATERIAL STRUCTURES Ergül, Özgür Salih (2013-11-09) A parallel implementation of the multilevel fast multipole algorithm (MLFMA) is developed for fast and accurate solutions of electromagnetics problems involving complex plasmonic metamaterial structures. Composite objects that consist of multiple penetrable regions, such as dielectric, lossy, and plasmonic parts, are formulated rigorously with surface integral equations and solved iteratively via MLFMA. Using the hierarchical strategy for the parallelization, the developed implementation is capable of simul...
Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms Dokeroglu, Tansel; Coşar, Ahmet (2014-09-01) The well-known one-dimensional Bin Packing Problem (BPP) of whose variants arise in many real life situations is a challenging NP-Hard combinatorial optimization problem. Metaheuristics are widely used optimization tools to find (near-) optimal solutions for solving large problem instances of BPP in reasonable running times. With this study, we propose a set of robust and scalable hybrid parallel algorithms that take advantage of parallel computation techniques, evolutionary grouping genetic metaheuristics,...
Broadband Analysis of Multiscale Electromagnetic Problems: Novel Incomplete-Leaf MLFMA for Potential Integral Equations Khalichi, Bahram; Ergül, Özgür Salih; Takrimi, Manouchehr; Erturk, Vakur B. (2021-12-01) Recently introduced incomplete tree structures for the magnetic-field integral equation are modified and used in conjunction with the mixed-form multilevel fast multipole algorithm (MLFMA) to employ a novel broadband incomplete-leaf MLFMA (IL-MLFMA) to the solution of potential integral equations (PIEs) for scattering/radiation from multiscale open and closed surfaces. This population-based algorithm deploys a nonuniform clustering that enables to use deep levels safely and, when necessary, without compromi...
Basis reduction and the complexity of branch-and-bound Pataki, Gábor; Tural, Mustafa Kemal; Wong, Erick B. (2010-05-06) The classical branch-and-bound algorithm for the integer feasibility problem [GRAPHICS] has exponential worst case complexity. We prove that, it. is surprisingly efficient on reformulations of (01), in which the columns of the constraint, matrix are short and near orthogonal, i e, a reduced basis of the generated lattice. when the entries of A ale from {1, ,M} for a large enough M, branch-and-bound solves almost all reformulated instances at the root. node For all A matrices we prove an upper bound on th...

Citation Formats

C. F. Bazlamaçcı, “Minimum-weight spanning tree algorithms - A survey and empirical study,” COMPUTERS & OPERATIONS RESEARCH, pp. 767–785, 2001, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/54393.