Models and algorithms for the weighted safe set problem

DOI10.1016/J.DAM.2022.12.022MaRDI QIDQ2686129zbMATH OpenOpenAlexFDO

Authors Enrico Malaguti, Vagner Pedrotti

Publication date 24 February 2023

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

Full work available at URL https://doi.org/10.1016/j.dam.2022.12.022

zbMATH Keywords

computational experimentsbranch-and-cut algorithmsafe set problemweighted safe set problem

Mathematics Subject Classification ID

Operations research and management science (90Bxx) Graph theory (05Cxx) Mathematical programming (90Cxx)

Recommendations

• A new formulation for the safe set problem on graphs
• A compact mixed integer linear formulation for safe set problems
• Approximating connected safe sets in weighted trees
• Safe set problem on graphs
• Safe sets, network majority on weighted trees

Cites work

• A compact mixed integer linear formulation for safe set problems
• A new formulation for the safe set problem on graphs
• Multi-neighborhood tabu search for the maximum weight clique problem
• Network majority on tree topological network
• On integer and bilevel formulations for the \(k\)-vertex cut problem
• On the minimum cut separator problem
• Parameterized complexity of safe set
• Safe set problem on graphs
• Safe sets in graphs: graph classes and structural parameters
• Thinning out Steiner trees: a node-based model for uniform edge costs

Cited in

(10)

• Safe sets, network majority on weighted trees
• Safe sets in graphs: graph classes and structural parameters
• Constructive-destructive heuristics for the safe set problem
• 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
• On the weighted safe set problem on paths and cycles
• A combinatorial branch and bound for the safe set problem
• scientific article; zbMATH DE number 6986946 (Why is no real title available?)
• Stable structure on safe set problems in vertex-weighted graphs

Describes a project that uses

Uses Software

• SCIP
• k-Vertex-Cut-Problem

This page was built for publication: Models and algorithms for the weighted safe set problem

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