An FPTAS for connectivity interdiction

DOI10.1007/978-3-031-59835-7_16MaRDI QIDQ7030559zbMATH OpenFDO

Authors Chien-Chung Huang, Nidia Obscura Acosta, Sorrachai Yingchareonthawornchai

Publication date 7 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-59835-7_16

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites work

• A survey of network interdiction models and algorithms
• An O(1)-approximation for minimum spanning tree interdiction
• Approximating \(k\)-edge-connected spanning subgraphs via a near-linear time LP solver
• Approximating the Held-Karp bound for metric TSP in nearly-linear time
• Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
• Computing All Small Cuts in an Undirected Network
• Connectivity interdiction
• Deterministic network interdiction
• Finding the most vital arcs in a network
• Hardness and approximation for network flow interdiction
• scientific article; zbMATH DE number 3705908 (Why is no real title available?)
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Matching interdiction
• Minimum cuts in near-linear time
• Modeling s-t path availability to support disaster vulnerability assessment of network infrastructure
• Optimal interdiction policy for a flow network
• The k most vital arcs in the shortest path problem

This page was built for publication: An FPTAS for connectivity interdiction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7030559)