10.1007/s11590-020-01597-w">
 

Multiple sink location problem in path networks with a combinational objective

Document Type

Article

Publication Date

2021

Department/School

Computer Science

Publication Title

Optimization Letters

Abstract

In this paper, we consider the k-sink location problem in a path network with the goal of optimizing a combinational function of the maximum completion time and the total completion time. Let P= (V, E) be an undirected path network with n vertices. Each vertex has a positive weight, indicating the initial amount of supplies, and each edge has a positive length and a uniform capacity, which is the maximum amount of supplies that can enter the edge per unit time. Our goal is to identify k sink locations on the path P so that all supplies will be successfully evacuated and the given objective function is optimized. This paper presents two efficient polynomial time algorithms, which achieve O(n) for k= 1 and O(n6) for general k, respectively.

Link to Published Version

10.1007/s11590-020-01597-w

Share

COinS