Decomposable trees: a polynomial algorithm for tripodes ?
In this article, we deal with graphs modelling interconnection networks of parallel systems (parallel computers, networks of workstations, etc.). We want to share the nodes of such a network between many users, each one needing a given number of nodes. Thus, a graph G with N vertices is said to be decomposable if for each set {n1,,nk} whose sum is equal to N, there exists a partition V1,,Vk of V(G) such that for each i, 1?i?k, |Vi|=ni and the subgraph induced by Vi is connected. We show that determining whether a given tripode (three disjoint chains connected by one extremity to a same new vertex) is decomposable can be done by a polynomial algorithm.
polynomial algorithm tripodes parallel systems network sharing graph decomposition integer decomposition