IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v35y2018i4d10.1007_s10878-018-0256-z.html
   My bibliography  Save this article

Integer programming approach to static monopolies in graphs

Author

Listed:
  • Babak Moazzez

    (Kennesaw State University)

  • Hossein Soltani

    (Urmia University of Technology)

Abstract

A subset M of vertices of a graph is called a static monopoly, if any vertex v outside M has at least $$\lceil \tfrac{1 }{2}\deg (v)\rceil $$ ⌈ 1 2 deg ( v ) ⌉ neighbors in M. The minimum static monopoly problem has been extensively studied in graph theoretical context. We study this problem from an integer programming point of view for the first time and give a linear formulation for it. We study the facial structure of the corresponding polytope, classify facet defining inequalities of the integer programming formulation and introduce some families of valid inequalities. We show that in the presence of a vertex cut or an edge cut in the graph, the problem can be solved more efficiently by adding some strong valid inequalities. An algorithm is given that solves the minimum monopoly problem in trees and cactus graphs in linear time. We test our methods by performing several experiments on randomly generated graphs. A software package is introduced that solves the minimum monopoly problem using open source integer linear programming solvers.

Suggested Citation

  • Babak Moazzez & Hossein Soltani, 2018. "Integer programming approach to static monopolies in graphs," Journal of Combinatorial Optimization, Springer, vol. 35(4), pages 1009-1041, May.
    • Handle: RePEc:spr:jcomop:v:35:y:2018:i:4:d:10.1007_s10878-018-0256-z
    DOI: 10.1007/s10878-018-0256-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-018-0256-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-018-0256-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Cheng-Lung Chen & Eduardo L. Pasiliao & Vladimir Boginski, 2023. "A polyhedral approach to least cost influence maximization in social networks," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-31, January.
    2. Hossein Soltani & Babak Moazzez, 2019. "A polyhedral study of dynamic monopolies," Annals of Operations Research, Springer, vol. 279(1), pages 71-87, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:35:y:2018:i:4:d:10.1007_s10878-018-0256-z. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.