AMORE - Publications

Theses

  1. M. Gantenbein: The Train Length Problem.
    Diploma Thesis, CS, ETH Zürich, 2001. (This thesis was awarded with the "Fritz-Kutter-Preis").

  2. Jan-Willem Goossens: Models and Algorithms for Railway Line Planning Problems.
    Phd Thesis, 2004 (to appear).

  3. D. Maleas: Dynamic Flows in Networks: Algorithms and Implementations.
    MSc. Thesis, Dept of Computer Engineering and Informatics, University of Patras, September 2001.

  4. Leon Peeters: Cyclic Railway Timetable Optimization.
    Phd Thesis, ERIM PhD Series Research in Management, Rotterdam, The Netherlands, 2003.

  5. Grigorios Prasinos, Implementation and Experimental Evaluation of the Planar Separator Algorithm and its Applications.
    MSc. Thesis, Dept of Computer Engineering and Informatics, University of Patras, March 2002.

Publications in Journals and Conference Proceedings

  1. E. Abbink, B. van den Berg, L.G. Kroon and M. Salomon: Allocation of Railway Rolling Stock for Passenger Trains.
    Transportation Science, vol. 38, pp. 33-41, 2004.

  2. L. Anderegg, S. Eidenbenz, M. Gantenbein, C. Stamm, D.S. Taylor, B. Weber, P. Widmayer: Train Routing Algorithms: Concepts, Design Choices, and Practical Considerations.
    In: Proceedings 5th Workshop on Algorithm Engineering and Experiments (ALENEX03), 2003.

  3. L. Anderegg, P. Penna, P. Widmayer: Online Train Disposition: to wait or not to wait?
    In: Proceedings of ATMOS'02, ICALP 2002 Satellite Workshop on Algorithmic Methods and Models for Optimization of Railways, Electronic Notes in Theoretical Computer Science, Vol 66, No. 6, 2002.

  4. D. Bjorner: New Results and Trends in Formal Techniques and Tools for the Development of Software for Transportation Systems --- A Review.
    In FORMS2003: Symposium on Formal Methods for Railway Operation and Control Systems, May 15-16, 2003. Publ. L'Harmattan Hongrie.

  5. Ulrik Brandes, Frank Schulz, Dorothea Wagner, and Thomas Willhalm: Generating node coordinates for shortest-path computations in transportation networks.
    ACM Journal on Experimental Algorithmics, 9:R1. ACM, 2004 (to appear).

  6. Gerth Brodal and Riko Jacob: Time-dependent networks as models to achieve fast exact time-table queries.
    In: Proceedings of ATMOS Workshop 2003, volume 92 of Electronic Notes in Theoretical Computer Science. Elsevier, 2004.

  7. I. Chatzigiannakis, S. Nikoletseas, N. Paspallis, P. Spirakis, and C. Zaroliagis: An Experimental Study of Basic Communication Protocols in Ad-Hoc Mobile Networks.
    Algorithm Engineering - WAE 2001, Lecture Notes in Computer Science Vol. 2141, pp. 159-171, Springer-Verlag, 2001.

  8. S. Cicerone, G. Di Stefano: Networks with Small Stretch Number.
    To be published on JDA.

  9. Sabine Cornelsen and Gabriele Di Stefano: Treelike Graphs: Characterization, Recognition, and Application.
    In: Proc. 30th Intl. Workshop on Graph-Theoretic Concepts in Computer Science (WG 2004), Springer Lecture Notes in Computer Science (to appear).

  10. S. Eidenbenz, A. Pagourtzis, P. Widmayer: Flexible Train Rostering.
    In: Proceedings of ISAAC 2003, Lecture Notes in Computer Science. Springer, 2003.

  11. T. Erlebach, M. Gantenbein, D. Huerlimann, G. Neyer, A. Pagourtzis, P. Penna, K. Schlude, K. Steinhoefel, D. Taylor, P. Widmayer: On the complexity of train assignment problems.
    In: Proceedings of ISAAC 01, Lecture Notes in Computer Science volume 2223, pages 390 - 402, Springer-Verlag, 2001. (appeared also as Technical Report 363, CS, ETH Zuerich 2001;

  12. Thomas Erlebach, Aris Pagourtzis, Katerina Potika, and Stamatis Stefanakos: Limited bandwidth in multiple-fiber all-optical caterpillars: a minimization problem.
    In: Proceedings of the 1st Balkan Conference on Informatics (BCI 2003), pp. 133-146, November 2003.

  13. Thomas Erlebach, Aris Pagourtzis, Katerina Potika, and Stamatis Stefanakos: Resource Allocation Problems in Multifiber WDM Tree Networks.
    In: Proceedings of 29th Workshop on Graph Theoretic Concepts in Computer Science (WG 2003)}, Lecture Notes in Computer Science, volume 2880, pp. 218-229. Springer, 2003.
    Full version available as TIK Technical Report Nr. 178, August 2003.

  14. D. Frigioni, T. Miller, U. Nanni, and C. Zaroliagis: An Experimental Study of Dynamic Algorithms for Transitive Closure.
    ACM Journal of Experimental Algorithmics, Vol.6, 2001.

  15. M. Gatto, R. Jacob, L. Peeters, and P. Widmayer: Delay Management: Exploring its Algorithmic Complexity.
    Accepted for SWAT 2004.

  16. H.W. Hamacher, A. Liebers, A. Schöbel, D. Wagner, F. Wagner: Locating New Stops in a Railway Network.
    Proceedings of the 1st Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'01), Electronic Notes in Theoretical Computer Science. Elsevier, 2001.

  17. Martin Holzer, Frank Schulz, and Thomas Willhalm: Combining speed-up techniques for shortest-path computations.
    In: Proc. III Workshop on Efficient and Experimental Algorithms (WEA'04), Lecture Notes in Computer Science. Springer, 2004 (to appear).

  18. Shahid Jabbar, Stefan Edelkamp, and Thomas Willhalm: Geometric travel planning.
    In: Proc. International Conference on Intelligent Transportation Systems, volume 2, pages 964-969. IEEE, 2003.

  19. A. Kaporis, C.~Makris, S. Sioutas, A. Tsakalidis, K. Tsichlas, and C. Zaroliagis: Improved Bounds for Finger Search on a RAM.
    In: Algorithms -- ESA 2003 (Design and Analysis Track), volume 2832 of Lecture Notes in Computer Science, pp.~325-336. Springer-Verlag, 2003.

  20. E. Konstantinou, Y. Stamatiou, and C. Zaroliagis: On the Construction of Prime Order Elliptic Curves.
    In: Progress in Cryptology - INDOCRYPT 2003, volume 2904 of Lecture Notes in Computer Science, pp. 309-322. Springer-Verlag, 2003.

  21. E. Kranakis, P. Penna, K. Schlude, D. Taylor, P. Widmayer: Improving Customer Proximity to Railway Stations.
    In: Proceedings of 5th Conference on Algorithms and Complexity, Lecture Notes in Theoretical Computer Science, volume 2653, Springer-Verlag, 2003.
    [html]

  22. L.G. Kroon and M. Fischetti: Crew scheduling for Netherlands Railways: "Destination: Customer".
    J. Daduna en S. Voss (eds.), Computer Aided Scheduling of Public Transport, Springer-Verlag, 2001. ISBN 3-540-42243-9.

  23. L.G. Kroon and M. Fischetti: Scheduling train drivers and guards: the Dutch Noord-Oost case.
    Proceedings of the 33rd HICSS conference, Hawaii 2000.

  24. Leo Kroon and Leon Peeters: A Variable Trip Time Model for Cyclic Railway Timetabling.
    Transportation Science 37(2), pp. 198-212, 2003.

  25. Flavia Mammana, Steffen Mecke, and Dorothea Wagner: The Station Location Problem on Two Intersecting Lines.
    In: Proceedings of ATMOS Workshop 2003, volume 92 of Electronic Notes in Theoretical Computer Science. Elsevier, 2004.

  26. S. Nikoletseas, G. Prasinos, P. Spirakis, and C. Zaroliagis: Attack Propagation in Networks.
    Proc. 13th ACM Symposium on Parallel Algorithms and Architectures - SPAA 2001, ACM Press, 2001.

  27. S. Nikoletseas, G. Prasinos, P. Spirakis, and C. Zaroliagis: Attack Propagation in Networks.
    In: Theory of Computing Systems, volume 36, pp.553 574, Special Issue on SPAA 2001, 2003.

  28. A. Pagourtzis, P. Penna,K. Schlude, K. Steinhöfel, D. Taylor, P. Widmayer: Server Placements, Roman Domination and Other Dominating Set Variants
    In: Proceedings of the 2nd International Conference on Theoretical Computer Science (TCS 2002), pp. 280-291, Kluwer, 2002.
    (A previous version appeared as Technical Report 365, CS, ETH Zuerich 2001.)

  29. L. Peeters and L.G. Kroon: A cycle based optimization model for cyclic railway timetabling.
    J. Daduna en S. Voss (eds.), Computer Aided Scheduling of Public Transport, Springer-Verlag, 2001. ISBN 3-540-42243-9.

  30. M. Penicka, A.K. Strupchanska, and D. Bjorner: Train maintenance routing.
    In FORMS2003: Symposium on Formal Methods for Railway Operation and Control Systems, May 15-16, 2003. Publ. L'Harmattan Hongrie.

  31. Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis: Experimental comparison of shortest path approaches for timetable information.
    In: Proceedings 5th Workshop on Algorithm Engineering and Experiments (ALENEX), 2004 (to appear).

  32. Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis: Efficient Models for Timetable Information in Public Transportation Systems.
    ACM Journal of Experimental Algorithmics, invited to the special issue on ALENEX 2004.

  33. Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis: Towards realistic modeling of time-table information through the time-dependent approach.
    In: Proceedings of ATMOS Workshop 2003, volume 92 of Electronic Notes in Theoretical Computer Science, pages 85-103. Elsevier, 2004.

  34. F. Schulz, D. Wagner, and C. Zaroliagis: Using Multi-Level Graphs for Timetable Information in Railway Systems.
    Algorithm Engineering and Experiments - ALENEX 2002, Lecture Notes in Computer Science, Springer-Verlag, 2002.

  35. A.K. Strupchanska, M. Penicka, and D. Bjorner: Railway staff rostering.
    In FORMS2003: Symposium on Formal Methods for Railway Operation and Control Systems, May 15-16, 2003. Publ. L'Harmattan Hongrie.

  36. Dorothea Wagner and Thomas Willhalm: Geometric speed-up techniques for finding shortest paths in large sparse graphs.
    In: Proc. 11th European Symposium on Algorithms (ESA 2003), volume 2832 of Lecture Notes in Computer Science, pages 776-787. Springer, 2003.

  37. Dorothea Wagner, Thomas Willhalm, and Christos Zaroliagis: Dynamic shortest path containers.
    In: Proc. Algorithmic MeThods and Models for Optimization of RailwayS (ATMOS 2003), volume 92 of Electronic Notes in Theoretical Computer Science, pages 65-84, Elsevier, 2004.

  38. C. Zaroliagis: Implementations and Experimental Studies of Dynamic Graph Algorithms. Chapter 11, in Experimental Algorithmics - From Algorithm Design to Robust and Efficient Software Eds. R. Fleischer, B. Moret, and E. Meineche-Schmidt, pp. 229-278, Springer-Verlag, 2002.

  39. Zwaneveld, P.J., L.G. Kroon, and S. van Hoesel: Routing trains through a railway station based on a Node Packing model.
    European Journal of Operational Research, 128: 14-33, 2001.

Technical Reports

  1. L. Anderegg, M. Gantenbein, D. Taylor, B. Weber, P. Widmayer: Car Routing Algorithms: Concepts, Design Choices, and Practical Considerations.
    Submitted.

  2. M. Cieliebak, T. Erlebach, F. Hennecke, B. Weber, and P. Widmayer: Scheduling with Release Times and Deadlines on a Minimum Number of Machines.
    Technical Report.

  3. R. Dekkerand and M.J.C.M. Vromans: Punctualiteit in het reizigersvervoer per trein (Punctuality in railway passenger transportation).
    In: M.R. de Graeff (ed.). Betrouwbaarheid van technische systemen (Reliability of technical systems), Stichting Toekomstbeeld der Techniek, The Hague, 2001 (In Dutch), ISBN 90-804496-5-2.

  4. D. Frigioni, T. Miller, U. Nanni, and C. Zaroliagis: An Experimental Study of Dynamic Algorithms for Transitive Closure.
    CTI Technical Report TR 2000/08/03, August 2000.

  5. J.H.M. Goossens, S. van Hoesel, and L.G. Kroon: A Branch-and-Cut approach for solving line planning problems.
    METEOR Research Memorandum RM/01/016}, University of Maastricht, 2001. Submitted to: Transportation Science.

  6. G. Hadjicharalambous, P. Pop, E. Pyrga, G. Tsaggouris, and C. Zaroliagis: The Railway Travelling Salesman Problem.
    In preparation, 2004.

  7. Matthias Hengartner: Darstellung von Eisenbahn-Infrastrukturelementen mittels XML-basierten Datenformaten.
    IVT 2002 (in German).

  8. P. Karras and D. Bjorner: Train composition and decomposition: From passenger statistics to schedules.
    Technical report, Informatics and Mathematical Modelling, Building 322, Richard Petersens Plads, Technical University of Denmark, DK--2800 Kgs.Lyngby, Denmark, 2002.

  9. L.G. Kroon: Opsporen van sneller en beter: modelling through... (Searching for faster and better: modelling through...).
    Inaugural Address, Erasmus University Rotterdam, September 21, 2001 (In Dutch).

  10. R.M. Lentink, P.-J. Fioole, L.G. Kroon, and C. van 't Woudt: Applying Operations Research techniques to planning of train shunting.
    Technical Report ERS-2003-094-LIS, Erasmus University Rotterdam, 2003.

  11. C. Liebchen and L. Peeters: On Cyclic Timetabling and Cycles in Graphs.
    Research Report, Institut für Mathematik 761/2002, Berlin, Germany, 2002.
    Submitted to Discrete Applied Mathematics.

  12. Csaba Megyeri: Bicriterial Delay Management.
    Technical Report No. 198, Konstanzer Schriften, 2004.
    [ html ]

  13. M. Peeters and L.G. Kroon: Circulation of Railway Rolling Stock: a Branch-and-Price Approach.
    Technical Report ERS-2003-055-LIS, Erasmus University Rotterdam, 2003. Also submitted to Operations Research.

  14. Sonia Perez i Mansilla: Report on Disposition of trains.

  15. M.J.C.M. Vromans, R. Dekker and L.G. Kroon: Reliability and heterogeneity of railway services.
    Technical Report ERS-2003-090-LIS, Erasmus University Rotterdam, 2003.
    Also submitted to European Journal of Operational Research.

  16. Dorothea Wagner, Thomas Willhalm, and Christos Zaroliagis: Geometric shortest path containers.
    Technical Report 2004-5, University of Karlsruhe, Faculty of Informatics, 2004.