• Multicommodity flows over time...

Result: Multicommodity flows over time: Efficient algorithms and complexity

Title:
Multicommodity flows over time: Efficient algorithms and complexity
Authors:
HALL, Alex, HIPPLER, Steffen, SKUTELLA, Martin
Source:
Automata, languages and programming (ICALP 2003)Theoretical computer science. 379(3):387-404
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 18 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Divers, Miscellaneous, Algorithme, Algorithm, Algoritmo, Application, Aplicación, Caractéristique, Characteristic, Característica, Communication, Comunicación, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Coût, Costs, Coste, Dynamique, Dynamics, Dinámica, Flot réseau, Network flow, Flujo red, Informatique théorique, Computer theory, Informática teórica, Internet, Maximum, Máximo, Production, Producción, Routage, Routing, Enrutamiento, Régulation trafic, Traffic control, Regulación tráfico, Réseau communication, Communication network, Red de comunicación, Système commande, Control system, Sistema control, Système production, Production system, Sistema producción, Topologie circuit, Network topology, Trafic routier, Road traffic, Tráfico carretera, 68Wxx, Multiflot, Multicommodity flow, Problème NP, Système communication, Système réseau, Complexity, Dynamic flow, Efficient algorithm, Flow over time
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Institut für Theoretische Informatik, ETH Zentrum, CAB H 39.2, 8092 Zurich, Switzerland
Institut für Mathematik, Technische Universität Berlin, Strasse des 17. Juni 136, 10623 Berlin, Germany
Fachbereich Mathematik, Universitdt Dortmund, 44221 Dortmund, Germany
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18821600
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.18821600
Database:
PASCAL Archive

Further Information

Flow variation over time is an important feature in network flow problems arising in various applications such as road or air traffic control, production systems, communication networks (e.g. the Internet) and financial flows. The common characteristic are networks with capacities and transit times on the arcs which specify the amount of time it takes for flow to travel through a particular arc. Moreover, in contrast to static flow problems, flow values on arcs may change with time in these networks. While the 'maximum s-t-flow over time' problem can be solved efficiently and 'min-cost flows over time' are known to be NP-hard, the complexity of (fractional) 'multicommodity flows over time' has been open for many years. We prove that this problem is NP-hard, even for series-parallel networks, and present new and efficient algorithms under certain assumptions on the transit times or on the network topology. As a result, we can draw a complete picture of the complexity landscape for flow over time problems.