Multiple sink location problems in dynamic path networks

DOI10.1016/J.TCS.2015.05.053MaRDI QIDQ897956zbMATH OpenOpenAlexFDO

Authors Yuya Higashikawa, Mordecai J. Golin, Naoki Katoh

Publication date 8 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.05.053

zbMATH Keywords

dynamic networkevacuation planningsink location

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Recommendations

• Multiple sink location problems in dynamic path networks
• Minsum \(k\)-sink problem on dynamic flow path networks
• Minsum \(k\)-sink problem on path networks
• Almost linear time algorithms for minsum \(k\)-sink problems on dynamic flow path networks
• Improved algorithms for computing \(k\)-sink on dynamic flow path networks

Cites work

• An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
• Computing a Minimum Weightk-Link Path in Graphs with the Concave Monge Property
• Constructing maximal dynamic flows from static flows
• Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity
• Minimax regret 1-sink location problem in dynamic path networks
• Minimax regret 1-sink location problems in dynamic path networks
• Multiple sink location problems in dynamic path networks

Cited in

(18)

• Sink location problems in dynamic flow grid networks
• Submodularity property for facility locations of dynamic flow networks
• Maxstatic sink location problem with capacitated sinks
• Multiple sink location problem in path networks with a combinational objective
• Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
• The line-constrained maximum coverage facility location problem
• Minsum \(k\)-sink problem on path networks
• Capacity provisioning for evacuation on path networks
• Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
• Multi-depot traveling salesmen location problems on networks with special structure
• Distributed Evacuation in Graphs with Multiple Exits
• Sink location problems in dynamic flow grid networks
• An \(O(n^2\log^2 n)\) time algorithm for minmax regret minsum sink on path networks
• Sink location to find optimal shelters in evacuation planning
• Multiple sink location problems in dynamic path networks
• Minsum \(k\)-sink problem on dynamic flow path networks
• Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities
• Almost linear time algorithms for minsum \(k\)-sink problems on dynamic flow path networks

This page was built for publication: Multiple sink location problems in dynamic path networks

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