Integer programming models and algorithms for the graph decontamination problem with mobile agents

DOI10.1002/net.21460zbMath1269.68071OpenAlexW2071948224MaRDI QIDQ5326775

J. Cole Smith, Siqian Shen, John Penuel

Publication date: 6 August 2013

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.21460

zbMATH Keywords

integer programmingdecompositionNP-completenesscutting-plane algorithmgraph decontamination

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• The integer \(L\)-shaped method for stochastic integer programs with complete recourse
• An annotated bibliography on guaranteed graph searching
• Distributed chasing of network intruders
• Search for an immobile entity on a network
• Cutting plane algorithms for solving a stochastic edge-partition problem
• Note on a helicopter search problem on graphs
• Graph searching and a min-max theorem for tree-width
• The vertex separation and search number of a graph
• Fugitive-search games on graphs and related parameters
• Local majorities, coalitions and monopolies in graphs: A review
• Mixed-integer programming techniques for decomposing IMRT fluence maps using rectangular apertures
• On Rerouting Connection Requests in Networks with Shared Bandwidth
• Network search games, with arbitrary searcher starting point
• Hide-and-seek games on a tree to which Eulerian networks are attached
• Decontamination of hypercubes by mobile agents
• Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
• NETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITY
• DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS
• Tree Decontamination with Temporary Immunity
• The complexity of searching a graph
• Monotonicity in graph searching
• Rendezvous search on a graph
• Minimax Rendezvous on the Line
• The Rendezvous Search Problem
• Recontamination does not help to search a graph
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Integer programming models and algorithms for the graph decontamination problem with mobile agents