Integer programming approach to static monopolies in graphs

DOI10.1007/s10878-018-0256-zzbMath1387.90145OpenAlexW2786376884MaRDI QIDQ1752610

Babak Moazzez, Hossein Soltani

Publication date: 24 May 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-018-0256-z

zbMATH Keywords

integer programmingpolytopesvalid inequalitiescactus graphsmajority thresholdsstatic monopoly

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

A polyhedral study of dynamic monopolies ⋮ Facets of the dynamic monopoly polytope: linear ordering formulation ⋮ Monopoly ⋮ A polyhedral approach to least cost influence maximization in social networks

Uses Software

• NetworkX
• Gurobi
• Cbc
• PORTA
• CLP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A study of monopolies in graphs
• On dynamic monopolies of graphs with general thresholds
• Combinatorial model and bounds for target set selection
• On dynamic monopolies of graphs: the average and strict majority thresholds
• On the set covering polytope. II: Lifting the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On the global offensive alliance number of a graph
• A linear algorithm for finding a minimum dominating set in a cactus
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On the 0,1 facets of the set covering polytope
• On the facial structure of the set covering polytope
• On the set covering polytope: Facets with coefficients in \(\{0,1,2,3\}\)
• Combinatorial algorithms on a class of graphs
• Spread of influence in weighted networks under time and budget constraints
• ON DYNAMIC MONOPOLIES OF GRAPHS WITH PROBABILISTIC THRESHOLDS
• Cones of Matrices and Set-Functions and 0–1 Optimization

This page was built for publication: Integer programming approach to static monopolies in graphs