Approximating connected safe sets in weighted trees

DOI10.1016/j.dam.2019.11.017zbMath1440.05109arXiv1711.11412MaRDI QIDQ2184684

Stefan Ehard, Dieter Rautenbach

Publication date: 29 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.11412

zbMATH Keywords

block graph; safe set; connected safe set

Mathematics Subject Classification ID

05C05: Trees

05C82: Small world graphs, complex networks (graph-theoretic aspects)

05B05: Combinatorial aspects of block designs

90B10: Deterministic network models in operations research

05C22: Signed and weighted graphs

05C51: Graph designs and isomorphic decomposition

Related Items

Parameterized Complexity of Safe Set, Safe sets and in-dominating sets in digraphs, A combinatorial branch and bound for the safe set problem, On the connected safe number of some classes of graphs, Stable structure on safe set problems in vertex-weighted graphs, On the weighted safe set problem on paths and cycles

Cites Work

• Safe set problem on graphs
• Network majority on tree topological network
• Safe sets in graphs: graph classes and structural parameters
• On the weighted safe set problem on paths and cycles
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Safe sets, network majority on weighted trees
• Combinatorial optimization. Theory and algorithms.