Premium
Two algorithms for the subset interconnection design problem
Author(s) -
Prisner Erich
Publication year - 1992
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.3230220406
Subject(s) - steiner tree problem , interconnection , vertex connectivity , vertex (graph theory) , mathematics , combinatorics , generalization , graph , heuristic , algorithm , minimum spanning tree , partition (number theory) , set (abstract data type) , computer science , discrete mathematics , mathematical optimization , computer network , mathematical analysis , programming language
An NP‐complete generalization of the minimum spanning tree problem is considered. Given are a set of V , a cost function c: V × V → R + , and a collection { X 1 , …, X m } of subsets of V . A graph G with vertex set V is called feasible if every X i induces a connected subgraph of G . The minimum subset interconnection design problem is to find a feasible graph with a minimum cost sum. In this paper, two heuristic algorithms for the problem are given and analyzed. Several classes of input data for which one of the algorithms finds optimal or at least approximative solutions are presented.