Nili Guttmann-Beck ; Zeev Sorek ; Michal Stern - Clustered Spanning Tree - Conditions for Feasibility

dmtcs:4906 - Discrete Mathematics & Theoretical Computer Science, August 27, 2019, vol. 21 no. 1, ICGT 2018 - https://doi.org/10.23638/DMTCS-21-1-15
Clustered Spanning Tree - Conditions for FeasibilityArticle

Authors: Nili Guttmann-Beck ; Zeev Sorek ; Michal Stern 1

  • 1 Caesarea Rothschild Institute and Department of Computer Science

Let H =< V, S > be a hypergraph, where V is a set of vertices and S is a set of not necessarily disjoint clusters Si ⊆ V. The Clustered Spanning Tree problem is to find a spanning tree of G which satisfies that each cluster induces a subtree, when it exists. We provide an efficient and unique algorithm which finds a feasible solution tree for H when it exists, or states that no feasible solution exists. The paper also uses special structures of the intersection graph of H to construct a feasible solution more efficiently. For cases when the hypergraph does not have a feasible solution tree, we consider adding vertices to exactly one cluster in order to gain feasibility. We characterize when such addition can gain feasibility, find the appropriate cluster and a possible set of vertices to be added.


Volume: vol. 21 no. 1, ICGT 2018
Published on: August 27, 2019
Accepted on: June 27, 2019
Submitted on: October 22, 2018
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 1312 times.
This article's PDF has been downloaded 363 times.