論文

査読有り
2018年1月1日

Safe sets, network majority on weighted trees

Networks
  • Ravindra B. Bapat
  • ,
  • Shinya Fujita
  • ,
  • Sylvain Legay
  • ,
  • Yannis Manoussakis
  • ,
  • Yasuko Matsui
  • ,
  • Tadashi Sakuma
  • ,
  • Zsolt Tuza

71
1
開始ページ
81
終了ページ
92
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1002/net.21794
出版者・発行元
Wiley-Liss Inc.

Let G = (V, E) be a graph and let w : V → ℝ&gt
0 be a positive weight function on the vertices of G. For every subset X of V, let w(X) ≔ ∑v∈G w(v). A non-empty subset ∑ 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. If the subgraph G(S) induced by a weighted safe set S is connected, then the set S is called a weighted connected safe set. In this article, we show that the problem of computing the minimum weight of a safe set is NP-hard for trees, even if the underlying tree is restricted to be a star, but it is polynomially solvable for paths. We also give an O(n log n) time 2-approximation algorithm for finding a weighted connected safe set with minimum weight in a weighted tree. Then, as a generalization of the concept of a minimum safe set, we define the concept of a parameterized infinite family of proper central subgraphs on weighted trees, whose polar ends are the vertex set of the tree and the centroid points. We show that each of these central subgraphs includes a centroid point.

リンク情報
DOI
https://doi.org/10.1002/net.21794
ID情報
  • DOI : 10.1002/net.21794
  • ISSN : 1097-0037
  • ISSN : 0028-3045
  • SCOPUS ID : 85034268336

エクスポート
BibTeX RIS