Exact algorithms for the minimum cost vertex blocker clique problem

DOI10.1016/j.cor.2018.11.016zbMath1458.90618OpenAlexW2901722134WikidataQ128878476 ScholiaQ128878476MaRDI QIDQ1634092

Josephine Namayanja, Farzaneh Nasirian, Foad Mahdavi Pajouh

Publication date: 17 December 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2018.11.016

zbMATH Keywords

interdictioncombinatorial branch-and-boundlazy-fashioned branch-and-cutminimum cost vertex blocker clique problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items

Assistance and interdiction problems on interval graphs, On designing networks resilient to clique blockers, The complexity of blocking (semi)total dominating sets with edge contractions, Detecting a most closeness-central clique in complex networks, Using edge contractions to reduce the semitotal domination number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum edge blocker dominating set problem
• A class of algorithms for mixed-integer bilevel min-max optimization
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• Bound and exact methods for assessing link vulnerability in complex networks
• An integer programming framework for critical elements detection in graphs
• The most vital nodes with respect to independent set and vertex cover
• Complexity of the critical node problem over trees
• Matching interdiction
• On short paths interdiction problems: Total and node-wise limited interdiction
• Network flow interdiction on planar graphs
• 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
• Dynamic programming algorithms for the zero-one knapsack problem
• The most vital edges in the minimum spanning tree problem
• The maximum clique problem
• Deterministic network interdiction
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
• Exact identification of critical nodes in sparse networks via new compact formulations
• Clique-detection models in computational biochemistry and genomics
• Mining market data: a network approach
• Graph Theory for Systems Biology
• A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs
• Two extended formulations for cardinality maximum flow network interdiction problem
• Minimum vertex blocker clique problem
• Shortest-path network interdiction
• Increasing the Weight of Minimum Spanning Trees
• Reducibility among Combinatorial Problems
• Removing Arcs from a Network
• Optimal interdiction policy for a flow network
• On cliques in graphs