Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows

DOI10.1007/s00453-022-01083-yarXiv1803.09289OpenAlexW2795061728MaRDI QIDQ6107888

Di Chen, Mordecai J. Golin

Publication date: 28 June 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.09289

zbMATH Keywords

facility locationparametric searchtree partitioningdynamic flowssink evacuationconfluent flowstree centroid

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Minsum \(k\)-sink problem on path networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for the one-dimensional \(k\)-center problem
• Algorithms for uniform centered partitions of trees
• A shifting algorithm for constrained min-max partition on trees
• An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks
• Improved algorithms for computing minmax regret sinks on dynamic path and tree networks
• A survey of dynamic network flows
• Efficient implementation of a shifting algorithm
• Efficient continuous-time dynamic network flow algorithms
• The shifting algorithm technique for the partitioning of trees
• A comprehensive survey on the quickest path problem
• Improved algorithms for computing \(k\)-sink on dynamic flow path networks
• Meet and merge: approximation algorithms for confluent flows
• The Quickest Transshipment Problem
• An Introduction to Network Flows over Time
• (Almost) Tight bounds and existence theorems for single-commodity confluent flows
• Capacitated Confluent Flows: Complexity and Algorithms
• Shifting algorithms for tree partitioning with general weighting functions
• New Results on the Complexity of p-Centre Problems
• Combinatorial Optimization with Rational Objective Functions
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• A Shifting Algorithm for Min-Max Tree Partitioning
• Slowing down sorting networks to obtain faster sorting algorithms
• Sink Evacuation on Trees with Dynamic Confluent Flows
• Partitioning a graph into connected components with fixed centers and optimizing cost‐based objective functions or equipartition criteria
• Constructing Maximal Dynamic Flows from Static Flows
• Quickest Flows Over Time
• A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
• Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity
• An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees

This page was built for publication: Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows