Network Majority on Tree Topological Network

Bapat, R.B. and Fujita, S. and Legay, S. and Manoussakis, Y. and Matsui, Y. and Tuza, Zsolt (2016) Network Majority on Tree Topological Network. ELECTRONIC NOTES IN DISCRETE MATHEMATICS, 54. pp. 79-84. ISSN 1571-0653

Text 1_s2.0_S1571065316301093_main_u.pdf Restricted to Repository staff only Download (176kB) | Request a copy

Abstract

Let G=(V,E) be a graph, and w:V→Q>0 be a positive weight function on the vertices of G. For every subset X of V, let w(X)=∑v∈Gw(v). A non-empty subset S⊂V(G) is a weighted safe set if, for every component C of the subgraph induced by S and every component D of G\S, we have w(C)≥w(D) whenever there is an edge between C and D. In this paper we show that the problem of computing the minimum weight of a safe set is NP-hard for trees, even if the underlining tree is restricted to be a star, but it is polynomially solvable for paths. Then we define the concept of a parameterized infinite family of “proper central subgraphs” on trees, whose polar ends are the minimum-weight connected safe sets and the centroids. We show that each of these central subgraphs includes a centroid. We also give a linear-time algorithm to find all of these subgraphs on unweighted trees. © 2016 Elsevier B.V.

Actions (login required)

Edit Item