Minimum edge blocker dominating set problem

DOI10.1016/j.ejor.2015.05.037zbMath1346.90788OpenAlexW1949782199MaRDI QIDQ319914

Eduardo L. Pasiliao, Jose L. Walteros, Foad Mahdavi Pajouh, Vladimir L. Boginski

Publication date: 6 October 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2015.05.037

zbMATH Keywords

branch-and-cut algorithmNP-hardnesscritical elements detectionminimum weighted dominating setnetwork interdiction

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (13)

Minimum cost edge blocker clique problem ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ Integer programming methods for solving binary interdiction games ⋮ Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ On designing networks resilient to clique blockers ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ Using edge contractions to reduce the semitotal domination number

Uses Software

• SparseMatrix

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• An integer programming framework for critical elements detection in graphs
• The most vital nodes with respect to independent set and vertex cover
• On the complexity of the bondage and reinforcement problems
• An exact algorithm for minimum CDS with shortest path constraint in wireless networks
• Complexity of the critical node problem over trees
• Domination alteration sets in graphs
• Matching interdiction
• New dominating sets in social networks
• On short paths interdiction problems: Total and node-wise limited interdiction
• Detecting critical nodes in sparse graphs
• Blockers and transversals
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• The bondage number of a graph
• Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem
• Deterministic network interdiction
• Exact interdiction models and algorithms for disconnecting networks via node deletions
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• On bondage numbers of graphs: a survey with some comments
• Wireless networking, dominating and packing
• The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• The university of Florida sparse matrix collection
• Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Minimum vertex blocker clique problem
• Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
• Shortest-path network interdiction
• Removing Arcs from a Network
• Optimal interdiction policy for a flow network

This page was built for publication: Minimum edge blocker dominating set problem