Reformulations and complexity of the clique interdiction problem by graph mapping

DOI10.1016/j.dam.2021.06.008zbMath1548.90427MaRDI QIDQ6558672

Sara Mattia

Publication date: 20 June 2024

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

zbMATH Keywords

complexitybilevel programmingfacetsmaximum cliqueedge clique interdictionnode clique interdictionsingle level reformulation

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A class of algorithms for mixed-integer bilevel min-max optimization
• The most vital nodes with respect to independent set and vertex cover
• Topics on perfect graphs
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• Approximating maximum independent sets by excluding subgraphs
• The maximum clique problem
• An exact algorithm for the maximum stable set problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Foundations of bilevel programming
• A fast algorithm for the maximum clique problem
• The maximum clique interdiction problem
• A survey of network interdiction models and algorithms
• The polynomial hierarchy and a simple model for competitive analysis
• A Characterization of Block-Graphs
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Minimum vertex blocker clique problem
• Computing Vertex Connectivity: New Bounds from Old Techniques
• Reducibility among Combinatorial Problems
• A branch-and-cut algorithm for the maximum cardinality stable set problem

This page was built for publication: Reformulations and complexity of the clique interdiction problem by graph mapping