  


The Vertex kcut Problem
Denis Cornaz(denis.cornazdauphine.fr) Abstract: Given an undirected graph G = (V, E), a vertex kcut of G is a vertex subset of V the removing of which disconnects the graph in at least k connected components. Given a graph G and an integer k greater than or equal to two, the vertex kcut problem consists in finding a vertex kcut of G of minimum cardinality. We first prove that the problem is NPhard for any fixed k greater than or equal to three. We then present a compact formulation, and an extended formulation from which we derive a column generation and a branching scheme. Extensive computational results prove the effectiveness of the proposed methods. Keywords: Vertex Cut, MixedInteger Programming Models, Branch and Price, Exact Algorithms Category 1: Combinatorial Optimization Category 2: Combinatorial Optimization (Graphs and Matroids ) Category 3: Integer Programming Citation: Download: [PDF] Entry Submitted: 09/21/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  