Vertex downgrading to minimize connectivity

DOI10.1007/s10107-022-01824-5zbMath1517.90118arXiv1911.11229MaRDI QIDQ6038644

R. Ravi, Hassene Aissi, Da Qi Chen

Publication date: 2 May 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1911.11229

zbMATH Keywords

approximation algorithmnetwork interdictionvertex downgradingvertex interdiction

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching interdiction
• Network flow interdiction on planar graphs
• An improved approximation algorithm of MULTIWAY CUT.
• Connectivity interdiction
• Deterministic network interdiction
• A 2-Approximation Algorithm for the Directed Multiway Cut Problem
• Detecting high log-densities
• Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives
• Improved approximation for directed cut problems
• Relations between average case complexity and approximation complexity
• A problem in network interdiction
• Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut
• Hardness and approximation for network flow interdiction
• Shortest-path network interdiction
• Multiway cuts in node weighted graphs
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximation Algorithms and Hardness of the k -Route Cut Problem
• Improved Algorithms for MST and Metric-TSP Interdiction
• The network inhibition problem
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Improved Region-Growing and Combinatorial Algorithms for k-Route Cut Problems (Extended Abstract)
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• On the history of the transportation and maximum flow problems

This page was built for publication: Vertex downgrading to minimize connectivity