Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems

DOI10.1007/s10878-012-9469-8zbMath1288.90114OpenAlexW1983163843MaRDI QIDQ1944389

Cristina Bazgan, Sonia Toubaline, Daniel Vanderpooten

Publication date: 25 March 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9469-8

zbMATH Keywords

complexityapproximation\(p\)-median\(p\)-centermin edge and node blockermost vital edges and nodes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Interdicting facilities in tree networks, Bound and exact methods for assessing link vulnerability in complex networks, An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance, Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives, Critical edges for the assignment problem: complexity and exact resolution, Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance, Blockers for the stability number and the chromatic number, Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm, On the hardness of covering-interdiction problems

Cites Work

• On the hardness of approximating minimum vertex cover
• On short paths interdiction problems: Total and node-wise limited interdiction
• Blockers and transversals
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Some simplified NP-complete graph problems
• Deterministic network interdiction
• Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures
• On Syntactic versus Computational Views of Approximability
• Unnamed Item
• Unnamed Item