Variant Minimum Spanning Network Connectivity Problem

Abstract

Many Combinatorial programming problems are NP-hard (Non Linear Polynomial), and the theory of NP-completeness has reduced hopes that NP-hard problems can be solved within polynomials bounded computation times. Nevertheless, sub-optimal solutions are sometimes easy to find. Consequently, there is much interest in approximation and heuristic algorithms that can find near optimal solutions within reasonable running time. We consider a minimum spanning tree problem and apply the Lexi-Search algorithm base d on the Pattern Recognition which takes care of simple combinatorial structure of the problem and computational results are reported.

Keywords: Minimum Spanning Tree Problem, Lexi-Search, word, Pattern Recognition