English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We address the facility location problems on dynamic flow path networks. Adynamic flow path network consists of an undirected path with positive edgelengths, positive edge capacities, and positive vertex weights. A path can beconsidered as a road, an edge length as the distance along the road and avertex weight as the number of people at the site. An edge capacity limits thenumber of people that can enter the edge per unit time. In the dynamic flownetwork, given particular points on edges or vertices, called sinks, all thepeople evacuate from the vertices to the sinks as quickly as possible. Theproblem is to find the location of sinks on a dynamic flow path network in sucha way that the aggregate evacuation time (i.e., the sum of evacuation times forall the people) to sinks is minimized. We consider two models of the problem:the confluent flow model and the non-confluent flow model. In the former model,the way of evacuation is restricted so that all the people at a vertex have toevacuate to the same sink, and in the latter model, there is no suchrestriction. In this paper, for both the models, we develop algorithms whichrun in almost linear time regardless of the number of sinks. It should bestressed that for the confluent flow model, our algorithm improves upon theprevious result by Benkoczi et al. [Theoretical Computer Science, 2020], andone for the non-confluent flow model is the first polynomial time algorithm.

Almost Linear Time Algorithms for Minsum $k$-Sink Problems on Dynamic Flow Path Networks