A combinatorial branch and bound for the safe set problem

DOI10.1002/NET.22140MaRDI QIDQ6179692zbMATH OpenOpenAlexFDO

Authors Alberto Boggio Tomasaz, Roberto Cordone, Pierre Hosteins

Publication date 18 December 2023

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.22140

zbMATH Keywords

branch-and-boundgraph partitioningsafe set

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• A new formulation for the safe set problem on graphs
• Safe set problem on graphs
• Parameterized complexity of safe set
• Parameterized complexity of safe set
• A compact mixed integer linear formulation for safe set problems
• On the weighted safe set problem on paths and cycles
• Constructive-destructive heuristics for the safe set problem
• Models and algorithms for the weighted safe set problem
• Safe sets in graphs: graph classes and structural parameters
• Safe sets in graphs: graph classes and structural parameters

Cites work

• A compact mixed integer linear formulation for safe set problems
• A new formulation for the safe set problem on graphs
• Approximating connected safe sets in weighted trees
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Network majority on tree topological network
• On the hardness of approximating minimum vertex cover
• Parameterized complexity of safe set
• Random Graphs
• Safe set problem on graphs
• Safe sets in graphs: graph classes and structural parameters
• Stable structure on safe set problems in vertex-weighted graphs
• Stable structure on safe set problems in vertex-weighted graphs. II: Recognition and complexity

Cited in

(3)

• Constructive-destructive heuristics for the safe set problem
• Exact Computation of Maximal Invariant Sets for Safe Markov Chains—Lattice Theoretic Approach
• Safe sets and in-dominating sets in digraphs

This page was built for publication: A combinatorial branch and bound for the safe set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6179692)