Safe sets, network majority on weighted trees

DOI10.1002/net.21794zbMath1418.90051OpenAlexW2768650128MaRDI QIDQ5228508

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

Publication date: 12 August 2019

Published in: Networks (Search for Journal in Brave)

Full work available at URL: http://real.mtak.hu/89922/1/net.21794.pdf

zbMATH Keywords

approximation algorithmcentroidweighted treesafe setnetwork majority\(\mathcal{NP}\)-completeness

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Dynamic programming (90C39)

Related Items

Safe number and integrity of graphs ⋮ The connected critical node problem ⋮ Approximating connected safe sets in weighted trees ⋮ Safe sets and in-dominating sets in digraphs ⋮ Parameterized Complexity of Safe Set ⋮ Stable structure on safe set problems in vertex-weighted graphs ⋮ A compact mixed integer linear formulation for safe set problems ⋮ On the connected safe number of some classes of graphs