Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Electronic Notes in ...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Electronic Notes in Discrete Mathematics
Article . 2016 . Peer-reviewed
License: Elsevier TDM
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Hal
Conference object . 2016
Data sources: Hal
DBLP
Article . 2016
Data sources: DBLP
versions View all 3 versions
addClaim

Network Majority on Tree Topological Network

Authors: Ravindra B. Bapat 0001; Shinya Fujita 0001; Sylvain Legay; Yannis Manoussakis; Yasuko Matsui; Tadashi Sakuma; Zsolt Tuza;

Network Majority on Tree Topological Network

Abstract

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 ∈ G w ( 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.

Keywords

[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO] Computer Science [cs]

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    11
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
11
Top 10%
Top 10%
Average
gold