KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 02 Mar 2011 16:45:38 +0100Wed, 02 Mar 2011 16:45:38 +0100Reliable and Restricted Quickest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288
In a dynamic network, the quickest path problem asks for a path minimizing the time needed to send a given amount of flow from source to sink along this path. In practical settings, for example in evacuation or transportation planning, the reliability of network arcs depends on the specific scenario of interest. In this circumstance, the question of finding a quickest path among all those having at least a desired path reliability arises. In this article, this reliable quickest path problem is solved by transforming it to the restricted quickest path problem. In the latter, each arc is associated a nonnegative cost value and the goal is to find a quickest path among those not exceeding a predefined budget with respect to the overall (additive) cost value. For both, the restricted and reliable quickest path problem, pseudopolynomial exact algorithms and fully polynomial-time approximation schemes are proposed.Stefan Ruzika; Markus Thiemannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288Wed, 02 Mar 2011 16:45:38 +0100Min-Max Quickest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2249
In a dynamic network, the quickest path problem asks for a path such that a given amount of flow can be sent from source to sink via this path in minimal time. In practical settings, for example in evacuation or transportation planning, the problem parameters might not be known exactly a-priori. It is therefore of interest to consider robust versions of these problems in which travel times and/or capacities of arcs depend on a certain scenario. In this article, min-max versions of robust quickest path problems are investigated and, depending on their complexity status, exact algorithms or fully polynomial-time approximation schemes are proposed.Stefan Ruzika; Markus Thiemannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2249Fri, 19 Nov 2010 09:57:06 +0100Earliest Arrival Flows in Series-Parallel Graphs
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2137
We present an exact algorithm for computing an earliest arrival flow in a discrete time setting on series-parallel graphs. In contrast to previous results for the earliest arrival flow problem this algorithm runs in polynomial time.Stefan Ruzika; Heike Sperber; Mechthild Steinerreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2137Tue, 06 Oct 2009 15:31:20 +0200