Vertices removal for feasibility of clustered spanning trees

Let H=〈V,S〉 be a hypergraph, where V is a set of vertices and S={S1,…,Sm} is a set of not necessarily disjoint clusters Si⊆V such that ∪i=1mSi=V. The Clustered Spanning Tree problem is to find a tree spanning all the vertices in V which satisfies that each cluster induces a subtree, when it exists....

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2021-06, Vol.296, p.68-84
Main Authors: Guttmann-Beck, Nili, Rozen, Roni, Stern, Michal
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Clusters
Feasibility
Graph theory
Graphs
Intersections
Polynomials
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let H=〈V,S〉 be a hypergraph, where V is a set of vertices and S={S1,…,Sm} is a set of not necessarily disjoint clusters Si⊆V such that ∪i=1mSi=V. The Clustered Spanning Tree problem is to find a tree spanning all the vertices in V which satisfies that each cluster induces a subtree, when it exists. For cases when a given hypergraph does not have a feasible solution tree, we consider removing vertices from some clusters in order to gain feasibility. We provide a special layered graph to represent the intersections of the clusters and use this graph to find a suitable vertices removal which gains feasibility for the hypergraph. We consider how this approach manifests for different structures of hypergraphs using polynomial time algorithms.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2020.08.030