{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:09:20Z","timestamp":1761620960005},"reference-count":12,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5215,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1992,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An NP\u2010complete generalization of the minimum spanning tree problem is considered. Given are a set of <jats:italic>V<\/jats:italic>, a cost function <jats:italic>c: V<\/jats:italic> \u00d7 <jats:italic>V<\/jats:italic> \u2192 <jats:bold>R<\/jats:bold><jats:sup>+<\/jats:sup>, and a collection {<jats:italic>X<\/jats:italic><jats:sub>1<\/jats:sub>, \u2026, <jats:italic>X<\/jats:italic><jats:sub><jats:italic>m<\/jats:italic><\/jats:sub>} of subsets of <jats:italic>V<\/jats:italic>. A graph <jats:italic>G<\/jats:italic> with vertex set <jats:italic>V<\/jats:italic> is called <jats:italic>feasible<\/jats:italic> if every <jats:italic>X<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub> induces a connected subgraph of <jats:italic>G<\/jats:italic>. 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.<\/jats:p>","DOI":"10.1002\/net.3230220406","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T12:49:26Z","timestamp":1178974166000},"page":"385-395","source":"Crossref","is-referenced-by-count":11,"title":["Two algorithms for the subset interconnection design problem"],"prefix":"10.1002","volume":"22","author":[{"given":"Erich","family":"Prisner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90010-7"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/0401042"},{"key":"e_1_2_1_5_2","first-page":"117","article-title":"Propri\u00e9t\u00e9 de Helly et probl\u00e8mes de repr\u00e9sentation","volume":"260","author":"Duchet P.","year":"1978","journal-title":"Coll. Int. Paris\u2010Orsay"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90154-1"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1985.10011"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","article-title":"On the shortest spanning subtree of a graph and the travelling salesman problem","volume":"71","author":"Kruskal J. B.","year":"1956","journal-title":"Proc. Am. Math. Soc."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700027300"},{"key":"e_1_2_1_10_2","article-title":"Intersection\u2010representation of graphs in n\u2010cyclomatic graphs","author":"Prisner E.","journal-title":"Ars Comb."},{"key":"e_1_2_1_11_2","unstructured":"E.Prisner Familien zusammenh\u00e4ngender Teilgraphen eines Graphen und ihre Durchschnittsgraphen. Dissertation Universit\u00e4t Hamburg 1988."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230220406","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230220406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T11:13:50Z","timestamp":1698059630000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230220406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,7]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1992,7]]}},"alternative-id":["10.1002\/net.3230220406"],"URL":"https:\/\/doi.org\/10.1002\/net.3230220406","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,7]]}}}