Premium
On the generalized minimum spanning tree problem
Author(s) -
Myung YoungSoo,
Lee ChangHo,
Tcha DongWan
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230260407
Subject(s) - spanning tree , minimum spanning tree , node (physics) , integer programming , mathematics , distributed minimum spanning tree , kruskal's algorithm , steiner tree problem , k minimum spanning tree , linear programming , tree (set theory) , heuristic , connected dominating set , set (abstract data type) , graph , combinatorics , time complexity , mathematical optimization , undirected graph , computer science , k ary tree , tree structure , binary tree , structural engineering , engineering , programming language
This paper considers the Generalized Minimum Spanning Tree Problem (GMSTP). Given an undirected graph whose nodes are partitioned into mutually exclusive and exhaustive node sets, The GMSTP is then to find a minimum‐cost tree which includes exactly one node from each node set. Here, we show that the GMSTP is NP ‐hard and that unless P = NP no polynomial‐time heuristic algorithm with a finite worst‐case performance ratio can exist for the GMSTP. We present various integer programming formulations for the problem and compare their linear programming relaxations. Based on the tightest formulation among the ones proposed, a dual‐based solution procedure is developed and shown to be efficient from computing experiments.