A Survey of Earliest Arrival Flows and a Study of the Series-Parallel Case

  • This work is concerned with dynamic flow problems, especially maximal dynamic flows and earliest arrival flows - also called universally maximal flows. First of all, a survey of known results about existence, computation and approximation of earliest arrival flows is given. For the special case of series-parallel graphs a polynomial algorithm for computing maximal dynamic flows is presented and this maximal dynamic flow is proven to be an earliest arrival flow.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Author:Mechthild Steiner
URN (permanent link):urn:nbn:de:hbz:386-kluedo-16357
Document Type:Master's Thesis
Language of publication:English
Year of Completion:2009
Year of Publication:2009
Publishing Institute:Technische Universität Kaiserslautern
Granting Institute:Technische Universität Kaiserslautern
Tag:earliest arrival flow; maximal dynamic flow; series-parallel graphs
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik

$Rev: 12793 $