Approximating connected safe sets in weighted trees
From MaRDI portal
Publication:2184684
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
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.