Refine
Year of publication
- 2008 (2)
Language
- English (2)
Keywords
- Discrete flows over time (1)
- approximation (1)
- complexity (1)
- routing (1)
Application Area
- B (2)
We consider quickest flows within a new model that is based on transportation applications. In contrast to other models, it is forbidden to store flow in nodes and to cross nodes with more than one flow unit simultaneously. We work on undirected graphs. Grid graphs are of special interest because they typically arise in practice. Our model allows to close edges temporarily by time windows, and considers waiting on edges.
We solve several quickest s,t–flow problems without time windows polynomially. We prove that time windows make these problems NP–hard and even not approximable. In a multicommodity environment, all quickest flow variants are shown to be NP–hard even in grid graphs with uniform edge transit times. An alternative proof shows NP-hardness already for a small number of commodities in the case that waiting is not allowed and transit times are edge–specific. Finally, we propose two approximation algorithms in the case that time windows do not occur.
In the Minimum Strictly Fundamental Cycle Basis (MSFCB) problem one is looking for a spanning tree such that the sum of the lengths of its induced fundamental circuits is minimum.
We identify square planar grid graphs as being very challenging testbeds for the MSFCB. The best lower and upper bounds for this problem are due to Alon, Karp, Peleg, and West (1995) and to Amaldi et~al. (2004).
We improve significantly their bounds, both empirically and asymptotically. Ideally, these new benchmarks will serve as a reference for the performance of any new heuristic for the MSFCB problem which will be designed only in the future.