Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems

DOI10.1007/978-3-642-17458-2_20zbMath1311.90062OpenAlexW2117858572MaRDI QIDQ3066160

Sonia Toubaline, Daniel Vanderpooten, Cristina Bazgan

Publication date: 8 January 2011

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/5766

zbMATH Keywords

complexityapproximation1-median1-centermost vital edges and nodes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Interdicting facilities in tree networks ⋮ Minimum cost edge blocker clique problem ⋮ Minimum edge blocker dominating set problem ⋮ Critical edges/nodes for the minimum spanning tree problem: complexity and approximation ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ Integer programming methods for solving binary interdiction games ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem ⋮ On the hardness of covering-interdiction problems