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

DOI10.1007/S00453-022-01083-YMaRDI QIDQ6107888zbMATH OpenOpenAlexFDO

Authors 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

confluent flowsdynamic flowsfacility locationparametric searchsink evacuationtree centroidtree partitioning

Mathematics Subject Classification ID

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

Abstract: Let $T=(V,E)$ be a tree with associated costs on its subtrees. A minmax $k$-partition of $T$ is a partition into $k$ subtrees, minimizing the maximum cost of a subtree over all possible partitions. In the centered version of the problem, the cost of a subtree cost is defined as the minimum cost of "servicing" that subtree using a center located within it. The problem motivating this work was the sink-evacuation problem on trees, i.e., finding a collection of $k$-sinks that minimize the time required by a confluent dynamic network flow to evacuate all supplies to sinks. This paper provides the first polynomial-time algorithm for solving this problem, running in $OBigl(max(k,logn)knlo{g}^{4}nBigr)$ time. The technique developed can be used to solve any Minmax Centered $k$-Partitioning problem on trees in which the servicing costs satisfy some very general conditions. Solutions can be found for both the discrete case, in which centers must be on vertices, and the continuous case, in which centers may also be placed on edges. The technique developed also improves previous results for finding a minmax cost $k$-partition of a tree given the location of the sinks in advance.

Cites work

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

Cited in

(6)

• Minsum \(k\)-sink problem on path networks
• Sink Evacuation on Trees with Dynamic Confluent Flows
• Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
• Sink location problems in dynamic flow grid networks
• Faster algorithms for evacuation problems in networks with a single sink of small degree and bounded capacitated edges
• Minmax-regret k-sink location on a dynamic tree network with uniform capacities

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

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