A compact mixed integer linear formulation for safe set problems

DOI10.1007/S11590-020-01540-ZzbMath1459.90180OpenAlexW3004730365MaRDI QIDQ2228393

Pierre Hosteins

Publication date: 17 February 2021

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-020-01540-z

zbMATH Keywords

graph partitioningmixed integer linear programmingvariable reductionsafe setsymmetry-breakingnetwork controlconnected safe set

Mathematics Subject Classification ID

Mixed integer programming (90C11) Combinatorial optimization (90C27)

Related Items (4)

Constructive-destructive heuristics for the safe set problem ⋮ Models and algorithms for the weighted safe set problem ⋮ Safe sets and in-dominating sets in digraphs ⋮ A combinatorial branch and bound for the safe set problem

Cites Work

• Unnamed Item
• Safe set problem on graphs
• A genetic algorithm for a class of critical node problems
• An integer programming framework for critical elements detection in graphs
• Network majority on tree topological network
• Detecting critical nodes in sparse graphs
• Safe sets in graphs: graph classes and structural parameters
• The critical node detection problem in networks: a survey
• Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• On the approximability of positive influence dominating set in social networks
• A new formulation for the safe set problem on graphs
• The \(k\)-separator problem: polyhedra, complexity and approximation results
• The vertex \(k\)-cut problem
• The vertex separator problem: a polyhedral investigation
• The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm
• Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
• Positive Influence Dominating Set in Online Social Networks
• Safe sets, network majority on weighted trees
• Collective dynamics of ‘small-world’ networks

This page was built for publication: A compact mixed integer linear formulation for safe set problems