A rigorous analysis of the cavity equations for the minimum spanning tree
, 2008 We analyze a new general representation for the Minimum Weight Steiner Tree (MST) problem which translates the topological connectivity constraint into a set of local conditions which can be analyzed by the so called cavity equations techniques.
Bayati, M., Braunstein, A., Zecchina, R.
core +1 more source
Heuristics for Minimum Spanning K-tree Problem
Procedia Computer Science, 2014 AbstractIn this paper we consider the problem of finding a spanning k-tree of minimum weight in a complete weighted graph which has a number of applications in designing reliable telecommunication networks. This problem is known to be NP-hard. We propose four effective heuristics: the first heuristic is based on the idea of a well-known Prim's ...
Shangin, Roman E., Pardalos, Panos M.
openaire +1 more source
An Approximation Scheme for the Generalized Geometric Minimum Spanning Tree Problem with Grid Clustering [PDF]
This paper is concerned with a special case of the Generalized Minimum Spanning Tree Problem. The Generalized Minimum Spanning Tree Problem is de¯ned on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are ...
Feremans,Corinne, Grigoriev,Alexander
core +1 more source
Solving the minimum labelling spanning tree problem using hybrid local search [PDF]
, 2007 Given a connected, undirected graph whose edges are labelled (or coloured), the minimum labelling spanning tree (MLST) problem seeks a spanning tree whose edges have the smallest number of distinct labels (or colours).
Consoli, S +3 more
core
Fully dynamic maintenance of euclidean minimum spanning trees [PDF]
, 1992 We maintain the minimum spanning tree of a point set in the plane, subject to point insertions and deletions, in time O(n^5/6 log1^2/2 n) per update operation. No nontrivial dynamic geometric minimum spanning tree algorithm was previously known.
Eppstein, David
core
An approximation algorithm for the at least version of the generalized minimum spanning tree problem
Journal of Numerical Analysis and Approximation Theory, 2006 We consider the at least version of the Generalized Minimum Spanning Tree Problem, denoted by L-GMSTP, which consists in finding a minimum cost tree spanning at least one node from each node set of a complete graph with the nodes partitioned into a ...
Petrică C. Pop +2 more
doaj +2 more sources
Optimization Algorithm’s Problems: Comparison Study
Kurdistan Journal of Applied Research, 2017 Currently, in various fields and disciplines problem optimization are used commonly. In this concern, we have to define solutions which are two known concepts optimal or near optimal optimization problems in regards to some objects. Usually, it is surely
Rebaz M. Nabi +3 more
doaj +1 more source
Constant-Time Algorithms for Minimum Spanning Tree and Related Problems on Processor Array with Reconfigurable Bus Systems [PDF]
[[abstract]]A processor array with a reconfigurable bus system is a parallel computation model that consists of a processor array and a reconfigurable bus system.
Pan, Tien-Tai
core +1 more source
The Modified CW1 Algorithm for the Degree Restricted Minimum Spanning Tree Problem [PDF]
, 2013 Given edge weighted graph G (all weights are non-negative), The Degree Constrained Minimum Spanning Tree Problem is concerned with finding the minimum weight spanning tree T satisfying specified degree restrictions on the vertices.
Caccetta, L. (Louis) +1 more
core
The Minimum Consistent Spanning Subset Problem on Trees
Journal of Graph Algorithms and ApplicationsSummary: Given a vertex-colored edge-weighted graph, the minimum consistent subset (MCS) problem asks for a minimum subset \(S\) of vertices such that every vertex \(v\notin S\) has the same color as its nearest neighbor in \(S\). This problem is NP-complete. A recent result of \textit{S. Dey} et al. [Lect. Notes Comput. Sci. 12867, 204--216 (2021; Zbl
Biniaz, Ahmad, Khamsepour, Parham
openaire +2 more sources