An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks

DOI10.1016/j.dam.2006.04.010zbMath1130.90029OpenAlexW1997620066MaRDI QIDQ860399

Takeaki Uno, Kazuhisa Makino, Satoru Fujishige, Satoko Mamada

Publication date: 9 January 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.010

zbMATH Keywords

location problemtree networksdynamic flows

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Discrete location and assignment (90B80)

Related Items

Multiple sink location problem in path networks with a combinational objective ⋮ Minmax regret for sink location on dynamic flow paths with general capacities ⋮ Minimax regret 1-sink location problem with accessibility in dynamic general networks ⋮ Sink location to find optimal shelters in evacuation planning ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ Improved algorithms for computing minmax regret sinks on dynamic path and tree networks ⋮ Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows ⋮ Multiple sink location problems in dynamic path networks ⋮ Capacity provisioning for evacuation on path networks ⋮ Minimax regret 1-sink location problem in dynamic cycle networks ⋮ Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights ⋮ An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths ⋮ Minimax regret 1-median problem in dynamic path networks ⋮ Minsum \(k\)-sink problem on path networks ⋮ Minimax regret vertex 2-sink location problem in dynamic path networks ⋮ Almost linear time algorithms for minsum \(k\)-sink problems on dynamic flow path networks ⋮ The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths ⋮ Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities ⋮ The weighted \(k\)-center problem in trees for fixed \(k\) ⋮ Minimax regret 1-sink location problem in dynamic path networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of dynamic network flows
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• The Quickest Transshipment Problem
• Locating Sources to Meet Flow Demands in Undirected Networks
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Constructing Maximal Dynamic Flows from Static Flows
• A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS