Thomas Erlebach's Publications

The copyright of some of the papers available on this webpage is held by the respective publishers. In particular, some of the papers are published in the LNCS series of Springer-Verlag, and the copyright for these papers is held by Springer.

Edited Books and Special Issues

• Thomas Erlebach and Michael Segal (Eds.): Proceedings of the 18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS 2022), LNCS 13707, Springer Verlag, 2022.

• Leah Epstein and Thomas Erlebach (Eds.): WAOA 2018 Special Issue on Approximation and Online Algorithms. Theory of Computing Systems, January 2020.

• Leah Epstein and Thomas Erlebach (Eds.): Proceedings of the 16th International Workshop on Approximation and Online Algorithms (WAOA 2018), LNCS 11312, Springer Verlag, 2018.

• Thomas Erlebach and Giuseppe Persiano (Eds.): WAOA 2012 Special Issue. Theory of Computing Systems 56(1), January 2015.

• Amotz Bar-Noy, Thomas Erlebach, Magnús M. Halldórsson, Sotiris E. Nikoletseas, Pekka Orponen: Special Issue for Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities. Theoretical Computer Science 553:1, 2014. (Special issue for ALGOSENSORS 2011 and 2012)

• Thomas Erlebach and Giuseppe Persiano (Eds.): Proceedings of the 10th International Workshop on Approximation and Online Algorithms (WAOA 2012), LNCS 7846, Springer Verlag, 2013.

• Thomas Erlebach, Sotiris E. Nikoletseas, and Pekka Orponen (Eds.): Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2011), LNCS 7111, Springer, 2012.

• Thomas Erlebach and Marco Lübbecke (Eds.): Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2010), Dagstuhl OpenAccess Series in Informatics (OASIcs), Vol. 14, 2010.

• Yossi Azar and Thomas Erlebach (Eds.): ESA 2006 Special Issue. Algorithmica 53(4), April 2009.

• Thomas Erlebach and Christos Kaklamanis (Eds.): WAOA 2006 Special Issue. Theory of Computing Systems 45(3), October 2009.

• Hajo Broersma, Thomas Erlebach, Tom Friedetzky and Daniel Paulusma (Eds.): Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008), LNCS 5344, Springer Verlag, 2008.

• Thomas Erlebach and Christos Kaklamanis (Eds.): Proceedings of the 4th Workshop on Approximation and Online Algorithms (WAOA 2006), LNCS 4368, Springer Verlag, 2006.

• Yossi Azar and Thomas Erlebach (Eds.): Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006), LNCS 4168, Springer Verlag, 2006.

• Thomas Erlebach (Ed.): Proceedings of the Third Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN 2006), LNCS 4235, Springer Verlag, 2006.

• Thomas Erlebach and Giuseppe Persiano (Eds.): Proceedings of the Third Workshop on Approximation and Online Algorithms (WAOA 2005), LNCS 3879, Springer Verlag, 2006.

• Ulrik Brandes and Thomas Erlebach (Eds.): Network Analysis - Methodological Foundations, LNCS Tutorial 3418, Springer Verlag, 2005.

Book Reviews

• Thomas Erlebach: Book review: Tim Roughgarden, Selfish Routing and the Price of Anarchy, MIT Press, Cambridge, MA (2005). In: Operations Research Letters, Volume 35, Issue 3, May 2007, pages 418-419.

Publications of 2024

• Thomas Erlebach, Nils Morawietz, Petra Wolf: Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization. In: 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024). https://doi.org/10.4230/LIPIcs.SAND.2024.12 (Best Student Paper Award)

• Thomas Erlebach, Nils Morawietz, Jakob T. Spooner, Petra Wolf: A Cop and Robber Game on Edge-Periodic Temporal Graphs. Journal of Computer and System Sciences, Volume 144, September 2024. https://doi.org/10.1016/j.jcss.2024.103534

• Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, William K. Moses Jr: Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. In: 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024). https://doi.org/10.4230/LIPIcs.ICALP.2024.55

• Evripidis Bampis, Konstantinos Dogeas, Thomas Erlebach, Nichole Megow, Jens Schlöter, Amitabh Trehan:  Competitive Query Minimization for Stable Matching with One-Sided Uncertainty. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024).  https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.17
  Also: http://arxiv.org/abs/2407.10170 [cs.DS]

• Konstantinos Dogeas, Thomas Erlebach, Ya-Chun Liang: Scheduling with Obligatory Tests. In: 32nd Annual European Symposium on Algorithms (ESA 2024).  Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024).
  https://doi.org/10.4230/LIPIcs.ESA.2024.48
  Also: https://arxiv.org/abs/2406.16734 [cs.DS]

• C. Mommessin, T. Erlebach and N.V. Shakhlevich, Classification and evaluation of the algorithms for vector bin packing. Computers and Operations Research (2024).  https://doi.org/10.1016/j.cor.2024.106860

Publications of 2023

• Thomas Erlebach, Murilo de Lima, Nicole Megow, Jens Schlöter: Sorting and Hypergraph Orientation under Uncertainty with Predictions. In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023), 2023, pp. 5577-5585. DOI: https://doi.org/10.24963/ijcai.2023/619

• Thomas Erlebach, Jakob T. Spooner: Parameterised temporal exploration problems. Journal of Computer and System Sciences 135: 73-88, 2023. Special issue on SAND 2022. DOI: https://doi.org/10.1016/j.jcss.2023.01.003

• Thomas Erlebach, Michael Hoffmann, Murilo S. de Lima: Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries. Algorithmica 85(2): 406-443, 2023. DOI: https://doi.org/10.1007/s00453-022-01035-6

• Banu Baklan Sen, Öznur Yasar Diner, Thomas Erlebach: List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs. In: 29th International Conference on Computing and Combinatorics (COCOON 2023), Proceedings, Part I, LNCS 14422, Springer, 2023, 168-181. DOI: https://doi.org/10.1007/978-3-031-49190-0_12

Publications of 2022

• Thomas Erlebach, Kelin Luo, Frits C.R. Spieksma: Package Delivery Using Drones with Restricted Movement Areas. In: Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Seoul, Korea, 19-21 December 2022. LIPIcs 248, pp. 49:1-49:16, 2022. DOI:  https://doi.org/10.4230/LIPIcs.ISAAC.2022.49
  Also: https://arxiv.org/abs/2209.12314 [cs.DS]

• Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter: Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty.  In: Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022), Potsdam, Germany, September 5-7, 2022. LIPIcs 244, pp. 49:1--49:18, 2022. DOI: https://doi.org/10.4230/LIPIcs.ESA.2022.49
  Also: https://arxiv.org/abs/2206.15201 [cs.DS]

• Thomas Erlebach, Jakob T. Spooner: Exploration of k-edge-deficient temporal graphs. Acta Informatica 59:387–407, 2022. DOI: https://doi.org/10.1007/s00236-022-00421-5

• Thomas Erlebach, Jakob T. Spooner: Parameterized temporal exploration problems. 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), LIPIcs 221, pp. 15:1-15:17, 2022. DOI: https://doi.org/10.4230/LIPIcs.SAND.2022.15

• Kelin Luo, Thomas Erlebach, Yinfeng Xu: Car-sharing between two locations: Online scheduling with flexible advance bookings. Discrete Applied Mathematics 313:53-66, 2022. DOI: https://doi.org/10.1016/j.dam.2022.01.016

Publications of 2021

• Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter: Learning-Augmented Query Policies. arXiv:2011.07385 [cs.DS]

• Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, Jens Schlöter: Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty. In: 29th Annual European Symposium on Algorithms (ESA 2021), held online, September 6-10, 2021. LIPIcs 204, pp. 10:1-10:18, 2021. DOI: https://doi.org/10.4230/LIPIcs.ESA.2021.10 Also: arXiv:2107.00572 [cs.DS]

• Thomas Erlebach, Jakob Spooner: Exploration of k-Edge-Deficient Temporal Graphs. In: Proceedings of the 17th International Workshop on Algorithms and Data Structures (WADS), Halifax, Nova Scotia, Canada, August 9-11, 2021. LNCS 12808, Springer, 2021, pp. 371-384. DOI: https://doi.org/10.1007/978-3-030-83508-8_27

• Thomas Erlebach, Michael Hoffmann, Murilo S. de Lima: Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries. In: Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Saarland Informatics Campus, Saarbrücken, Germany, March 16-19, 2021. LIPIcs 187, pp. 27:1-27:18. DOI: https://doi.org/10.4230/LIPIcs.STACS.2021.27 Also: arXiv:2101.05032 [cs.DS]

• Thomas Erlebach, Michael Hoffmann and Frank Kammer: On temporal graph exploration. Journal of Computer and System Sciences, Volume 119, August 2021, pp. 1-18. Available online as pre-proof since 6 February 2021. https://doi.org/10.1016/j.jcss.2021.01.005
  Also: arXiv:1504.07976 [cs.DS]

• Amotz Bar-Noy, Thomas Erlebach, Dror Rawitz, Peter Terlecky: "Green" barrier coverage with mobile sensors. Theoretical Computer Science, Volume 860, March 2021, pp. 117-134. Available online since 26 January 2021. DOI: https://doi.org/10.1016/j.tcs.2021.01.034

• Thomas Erlebach: Algorithms that Access the Input via Queries. In: 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2021), Bolzano-Bozen, Italy, January 25-29, 2021. LNCS 12607, Springer, 2021, pp. 3-12. DOI: https://doi.org/10.1007/978-3-030-67731-2_1

Publications of 2020

• Iago A. Carvalho, Thomas Erlebach and Kleitos Papadopoulos: On the Fast Delivery Problem with One or Two Packages. Journal of Computer and System Sciences. Available online as pre-proof since 17 September 2020. Volume 115 (2021), pp. 246-263. https://doi.org/10.1016/j.jcss.2020.09.002

• Christoph Dürr, Thomas Erlebach, Nicole Megow and Julie Meißner: An Adversarial Model for Scheduling with Testing. Algorithmica. Volume 82, 2020, pp. 3630-3675. Available online since 10 July 2020. http://doi.org/10.1007/s00453-020-00742-2
  Also: arXiv:1709.02592 [cs.DS]

• Thomas Erlebach, Jakob T. Spooner: Non-Strict Temporal Exploration. In: Proceedings of the 27th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2020), LNCS 12156, Springer-Verlag, 2020, pp. 129-145. https://doi.org/10.1007/978-3-030-54921-3_8 

• Thomas Erlebach, Jakob T. Spooner: A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity. In: Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), Limassol, Cyprus, January 20-24, 2020, LNCS 12011, Springer, 2020, pages 64-75. https://doi.org/10.1007/978-3-030-38919-2_6
  Also: arXiv:1908.06828 [cs.DS]

Publications of 2019

• Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, Jakob T. Spooner: Two Moves per Time Step Make a Difference. In: Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP 2019), Patras, Greece, July 8-12, 2019. LIPIcs 141, pp. 141:1-141:14. https://doi.org/10.4230/LIPIcs.ICALP.2019.141 

• Iago A. Carvalho, Thomas Erlebach and Kleitos Papadopoulos:An Efficient Algorithm for the Fast Delivery Problem. In: Proceedings of the 22nd International Symposium on Fundamentals of Computation Theory (FCT 2019), Copenhagen, Denmark, August 11-14, 2019. LNCS 11651, Springer, 2019, pages 171-184.
  Also: arXiv:1904.09142 [cs.DS]

• Kelin Luo, Thomas Erlebach, Yinfeng Xu: Car-Sharing on a Star Network: On-line Scheduling with k Servers. In: Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), TU Berlin, Berlin, Germany, March 13-16, 2019. LIPIcs 126, 51:1-51:14. https://doi.org/10.4230/LIPIcs.STACS.2019.51

• Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordecai Shalom, Prudence Wong, Shmuel Zaks: Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals. Theoretical Computer Science 788:66-78, 8 October 2019 (Online First, 20 May 2019). https://doi.org/10.1016/j.tcs.2019.05.007

Publications of 2018

• Kelin Luo, Thomas Erlebach, Yinfeng Xu: Online Scheduling of Car-Sharing Requests between Two Locations with Many Cars and Flexible Advance Bookings. In: Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018), Jiaoxi, Yilan County, Taiwan, December 16-19, 2018, LIPIcs 123, 64:1-64:13. https://doi.org/10.4230/LIPIcs.ISAAC.2018.64

• Annette Ficker, Thomas Erlebach, Matus Mihalak and Frits Spieksma: Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm. In: Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018), Jiaoxi, Yilan County, Taiwan, December 16-19, 2018. LIPIcs 123, 45:1-45:12. https://doi.org/10.4230/LIPIcs.ISAAC.2018.45

• Kelin Luo, Thomas Erlebach, Yinfeng Xu: Car-Sharing between Two Locations: Online Scheduling with Two Servers. In: Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool (UK), August 27-31, 2018, LIPIcs 117, 50:1-50:14. https://doi.org/10.4230/LIPIcs.MFCS.2018.50

• Thomas Erlebach, Jakob Spooner: Faster Exploration of Degree-Bounded Temporal Graphs. In: Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool (UK), August 27-31, 2018. 36:1-36:13. https://doi.org/10.4230/LIPIcs.MFCS.2018.36

• Kelin Luo, Thomas Erlebach, Yinfeng Xu: Car-Sharing Between Two Locations: Online Scheduling with Flexible Advance Bookings. In: Proceedings of the 24th International Conference on Computing and Combinatorics (COCOON 2018), Qing Dao, China, July 2-4, 2018. Lecture Notes in Computer Science 10976, Springer, 2018, pp. 242-254. https://doi.org/10.1007/978-3-319-94776-1_21

• Christoph Dürr, Thomas Erlebach, Nicole Megow, Julie Meißner: Scheduling with Explorable Uncertainty. In: Proceedings of the 9th Innovations in Theoretical Computer Science (ITCS 2018) conference, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 94, 2018, pp. 30:1-30:14. https://doi.org/10.4230/LIPIcs.ITCS.2018.30
  Also: arXiv:1709.02592 [cs.DS]

Publications of 2017

• Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordecai Shalom, Prudence Wong, Shmuel Zaks: Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals. In: Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017). LNCS 10628, Springer, 2017, pages 317-332. https://doi.org/10.1007/978-3-319-71147-8_22

• Aeshah Alsughayyir, Thomas Erlebach: Online Algorithms for Non-preemptive Speed Scaling on Power-Heterogeneous Processors. In: Proceedings of the 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017). LNCS 10628, Springer, 2017, pages 457-465. https://doi.org/10.1007/978-3-319-71147-8_32

• Aeshah Alsughayyir, Thomas Erlebach: A Bi-objective Scheduling Approach for Energy Optimisation of Executing and Transmitting HPC Applications in Decentralised Multi-cloud Systems. In: Proceedings of the 16th International Symposium on Parallel and Distributed Computing (ISPDC-2017), IEEE, 2017, pages 44-53. https://doi.org/10.1109/ISPDC.2017.27

• Aisha Mashraqi, Thomas Erlebach: Throughput Improvement by Reducing Dropped Packets at Interface Queue (IFQ) in Multi-Channel Wireless Mesh Networks. In: Proceedings of the 14th International Symposium on Pervasive Systems, Algorithms, and Networks (I-SPAN 2017). IEEE, 2017, pages 140-147. https://doi.org/10.1109/ISPAN-FCST-ISCC.2017.47

• Aram Rasul and Thomas Erlebach: The extra-bit technique for reducing idle listening in data collection. Int. J. Sensor Networks, 25(1):31-44, January 2017. https://doi.org/10.1504/IJSNET.2016.10001535

Publications of 2016

• Thomas Erlebach, Michael Hoffmann and Frank Kammer: Query-Competitive Algorithms for Cheapest Set Problems under Uncertainty. Theoretical Computer Science 613:51-64, 1 February 2016. https://doi.org/10.1016/j.tcs.2015.11.025

• Thomas Erlebach: Algorithms for Queryable Uncertainty. In: Frontiers in Algorithmics, 10th International Workshop, FAW 2016, Qingdao, China, June 30-July 2, 2016, Proceedings. LNCS 9711, Springer 2016, pp. 1-7. https://doi.org/10.1007/978-3-319-39817-4_1

• Aeshah Alsughayyir, Thomas Erlebach: Energy Aware Scheduling of HPC Tasks in Decentralised Cloud Systems. In: Proceedings of the 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP 2016), 2016, pp. 617-621. https://doi.org/10.1109/PDP.2016.83

• Aisha Mashraqi, Thomas Erlebach: Delay and Interference Aware Metric in Multi-channel Wireless Mesh Network. In: Proceedings of the 15th Annual Wireless Telecommunications Symposium (WTS 2016). IEEE, 2017. https://doi.org/10.1109/WTS.2016.7948001

Publications of 2015

• Thomas Erlebach, Michael Hoffmann: Query-Competitive Algorithms for Computing with Uncertainty. In: The Algorithmics Column, Bulletin of the EATCS 116, June 2015.

• Thomas Erlebach, Matthew Radoja: Further Results on Capacitated Network Design Games. In: Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT 2015), LNCS 9347, Springer, 2015, pp. 57-68. https://doi.org/10.1007/978-3-662-48433-3_5

• Hasna Mohsen Alqahtani, Thomas Erlebach: Minimum Activation Cost Edge-Disjoint Paths in Graphs with Bounded Tree-Width. In: Proceedings of the 26th International Workshop on Combinatorial Algorithms (IWOCA 2015), LNCS 9538, Springer, 2016, pp. 13-24. https://doi.org/10.1007/978-3-319-29516-9_2

• Aram Rasul, Thomas Erlebach: An Energy Efficient and Restricted Tour Construction for Mobile Sink in Wireless Sensor Networks. In: IEEE MASS 2015, pp. 55-63. https://doi.org/10.1109/MASS.2015.41

• Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach, Maurizio Patrignani: Computational Complexity of Traffic Hijacking under BGP and S-BGP. Theoretical Computer Science 600:143-154, 4 October 2015 (available online 26 July 2015). https://doi.org/10.1016/j.tcs.2015.07.038

• Thomas Erlebach, Michael Hoffmann, and Frank Kammer: On Temporal Graph Exploration (pdf-file). In: Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP 2015), LNCS 9134, Springer, 2015, pp. 444-455.  https://doi.org/10.1007/978-3-662-47672-7_36
  Also: arXiv:1504.07976 [cs.DS]

Publications of 2014

• Aram Rasul and Thomas Erlebach: Reducing Idle Listening during Data Collection in Wireless Sensor Networks (pdf-file). In: Proceedings of the 10th International Conference on Mobile Ad-hoc and Sensor Networks (MSN 2014). IEEE, 2014, pp. 16-23. https://doi.org/10.1109/MSN.2014.10

• Thomas Erlebach and Michael Hoffmann: Minimum Spanning Tree Verification under Uncertainty (pdf-file). In: Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2014), LNCS 8747, Springer, 2014, pp. 164-175.

• Thomas Erlebach, Michael Hoffmann and Frank Kammer: Query-Competitive Algorithms for Cheapest Set Problems under Uncertainty (pdf-file). In: Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), LNCS 8635, Springer, 2014, pp. 263-274. https://doi.org/10.1007/978-3-662-44465-8_23

• Hasna Mohsen Alqahtani and Thomas Erlebach: Minimum Activation Cost Node-Disjoint Paths in Graphs with Bounded Treewidth (pdf-file). In: Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), LNCS 8327, Springer, 2014, pp. 65-76. https://doi.org/10.1007/978-3-319-04298-5_7

• S.D. Gunashekar, A. Das, T. Erlebach, and E.M. Warrington: An experimental study of small multi-hop wireless networks using chirp spread spectrum. Wireless Networks 20(1):89-103, 2014. https://doi.org/10.1007/s11276-013-0595-8

Publications of 2013

• Hasna Mohsen Alqahtani and Thomas Erlebach: Approximation algorithms for disjoint st-paths with minimum activation cost (pdf-file). In: Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC 2013).LNCS 7878, Springer, 2013, pp. 1-12. https://doi.org/10.1007/978-3-642-38233-8_1
  Erratum: There is a mistake in the proof of Lemma 1 in this paper. As a consequence, Lemma 1 and Theorem 1 are wrong, and the proofs of the results that are derived from them (Corollary 1 and Corollary 2) are not valid. I am very grateful to Dawood Kabha and Zeev Nutov for discovering this mistake and alerting me to it.

Publications of 2012

• Marco Chiesa, Giuseppe Di Battista, Thomas Erlebach, and Maurizio Patrignani: Computational Complexity of Traffic Hijacking under BGP and S-BGP. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), Part II. LNCS 7392, Springer, 2012, pp. 476-487. https://doi.org/10.1007/978-3-642-31585-5_43
  Also: arXiv:1205.4564 [cs.NI]

• S.D. Gunashekar, A. Das, T. Erlebach, and E.M. Warrington: A Simple Scheme to Improve the Throughput of Small Multi-hop Wireless Networks (pdf-file). In: Proceedings of the 8th International Symposium on Communication Systems, Networks & Digital Signal Processing (CSNDSP 2012), Poznan, Poland, 18-20 July 2012, IEEE, 2012. https://doi.org/10.1109/CSNDSP.2012.6292710

Publications of 2011

• Thomas Erlebach: Majority - Who Gets Elected Class Rep? In: B. Vöcking et al. (Eds.), Algorithms Unplugged, Springer, 2011.

• Thomas Erlebach, Tom Grant and Frank Kammer: Maximising lifetime for fault-tolerant target coverage in sensor networks (pdf-file). In: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011), ACM, 2011, pp. 187-196. https://doi.org/10.1145/1989493.1989521

• Thomas Erlebach, Tom Grant and Frank Kammer: Maximising lifetime for fault-tolerant target coverage in sensor networks (pdf-file). Sustainable Computing: Informatics and Systems 1(3):213-225, 2011. https://doi.org/10.1016/j.suscom.2011.05.005

• Jawad Ashraf and Thomas Erlebach: A Hybrid Scheduling Technique for Grid Workflows in Advance Reservation Environments. In: Proceedings of the 2011 International Conference on High Performance Computing & Simulation (HPCS 2011), IEEE, 2011, pp.98-106. https://doi.org/10.1109/HPCSim.2011.5999812

• Gunashekar, S.D.; Das, A.; Erlebach, T.; Warrington, E.M.: Wireless multi-hop throughput: Preliminary testbed measurements. Loughborough Antennas and Propagation Conference (LAPC), 2011. https://doi.org/10.1109/LAPC.2011.6114121

• Gunashekar, S.D.; Das, A.; Erlebach, T.; Warrington, E.M.: Wireless multi-hop throughput: Preliminary results from a simulation-based study. Loughborough Antennas and Propagation Conference (LAPC), 2011. https://doi.org/10.1109/LAPC.2011.6114122

• Jessica Chang, Thomas Erlebach, Renars Gailis and Samir Khuller: Broadcast Scheduling: Algorithms and Complexity (pdf-file). ACM Transactions on Algorithms 7(4), 2011. https://doi.org/10.1145/2000807.2000815

Publications of 2010

• Jawad Ashraf and Thomas Erlebach: A new resource mapping technique for Grid workflows in advance reservation environments. In: Proceedings of the 2010 International Conference on High Performance Computing & Simulation (HPCS 2010), IEEE, 2010, pp. 63-70. https://doi.org/10.1109/HPCS.2010.5547148

• Shagufta Henna and Thomas Erlebach: Congestion and network density adaptive broadcasting in mobile ad hoc networks. In: 11th Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD 2010). Studies in Computational Intelligence 295, Springer, Heidelberg, 2010, pp. 53-67. https://doi.org/10.1007/978-3-642-13265-0_5

• Shagufta Henna and Thomas Erlebach: CMAB: Cross Layer Mobility-Adaptive Broadcasting in Mobile Ad hoc Networks. In: 8th International Conference on Advances in Mobile Computing & Multimedia (MoMM 2010), 2010. https://doi.org/10.1145/1971519.1971538

• Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondrej Pangrac, Heiko Schilling, Martin Skutella: Length-Bounded Cuts and Flows (pdf-file). ACM Transactions on Algorithms 7(1), November 2010, Article No.: 4. https://doi.org/10.1145/1868237.1868241

• Luca Cittadini, Pino Di Battista, Thomas Erlebach, Maurizio Patrignani and Massimo Rimondini: Assigning AS Relationships to Satisfy the Gao-Rexford Conditions (pdf-file). In: Proceedings of the 18th IEEE International Conference on Network Protocols (ICNP 2010), IEEE, 2010. https://doi.org/10.1109/ICNP.2010.5762760

• Thomas Erlebach and Erik Jan van Leeuwen: PTAS for Weighted Set Cover on Unit Squares (pdf-file). In: Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010), LNCS 6302, Springer-Verlag, 2010, pp. 166-177. https://doi.org/10.1007/978-3-642-15369-3_13

• Thomas Erlebach and Tom Grant: Scheduling Multicast Transmissions Under SINR Constraints (pdf-file). In: Proceedings of the 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2010), LNCS 6451, Springer-Verlag, 2010, pp. 47-61. https://doi.org/10.1007/978-3-642-16988-5_5

• Ambreen Shahnaz and Thomas Erlebach: Approximating fault-tolerant Steiner subgraphs in heterogeneous wireless networks (pdf-file). In: Proceedings of the 6th International Wireless Communications and Mobile Computing Conference (IWCMC 2010), ACM, 2010, pp. 529-533. https://doi.org/10.1145/1815396.1815519

• Davide Bilo, Thomas Erlebach, Matus Mihalak and Peter Widmayer: Discovery of network properties with all-shortest-paths queries (pdf-file). Theoretical Computer Science 411(14-15):1626-1637, 2010. SIROCCO 2008 special issue. https://doi.org/10.1016/j.tcs.2010.01.010

• Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff and Alexander Wolff: Trimming of Graphs, with Application to Point Labeling (pdf-file). Theory of Computing Systems 47(3):613-636, 2010. STACS 2008 special issue. Published online February 2009 (Open Access!). https://doi.org/10.1007/s00224-009-9184-8

Publications of 2009

• Thomas Erlebach and Anna Mereu: Path Splicing with Guaranteed Fault Tolerance (pdf-file). In: Proceedings of IEEE GLOBECOM 2009. IEEE, 2009. https://doi.org/10.1109/GLOCOM.2009.5425984

• Thomas Erlebach and Matus Mihalak: A (4+epsilon)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs (pdf-file). In: Proceedings of the 7th Workshop on Approximation and Online Algorithms (WAOA 2009). LNCS 5893, Springer-Verlag, 2010, pp. 135-146. https://doi.org/10.1007/978-3-642-12450-1_13

• Thomas Erlebach and Ambreen Shahnaz: Approximating Node-Weighted Multicast Trees in Wireless Ad-Hoc Networks (pdf-file). In: Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing: Connecting the World Wirelessly (IWCMC 2009), ACM, 2009, pp. 639-643. https://doi.org/10.1145/1582379.1582518

• Leah Epstein, Thomas Erlebach, Asaf Levin: Online Capacitated Interval Coloring (pdf-file). SIAM Journal on Discrete Mathematics 23(2):822-841, 2009. https://doi.org/10.1137/070682496

• Thomas Erlebach, Linda Moonen, Frits Spieksma and Danica Vukadinovic: Connectivity Measures for Internet Topologies on the Level of Autonomous Systems (pdf-file). Operations Research 57(4):1006-1025, July-August 2009. https://doi.org/10.1287/opre.1080.0677

• Leah Epstein, Thomas Erlebach, Asaf Levin: Variable Sized Online Interval Coloring with Bandwidth (pdf-file). Algorithmica 53(3):385-401, 2009. Available online since 13 October 2007. https://doi.org/10.1007/s00453-007-9071-0

Publications of 2008

• Thomas Erlebach: Mehrheitsbetimmung - Wer wird Klassensprecher? (in German) In: B. Vöcking et al. (Eds.), Taschenbuch der Algorithmen, Springer, 2011.

• Davide Bilo, Thomas Erlebach, Matus Mihalak and Peter Widmayer: Discovery of Network Properties with All-Shortest-Paths Queries. In: Proceedings of the 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2008). LNCS 5058, Springer-Verlag, April 2008, pp. 89-103.  https://doi.org/10.1007/978-3-540-69355-0_9
  Extended version available as Technical Report 591, Institute of Theoretical Computer Science, ETH Zürich, May 2008. https://doi.org/10.3929/ethz-a-006821095 

• Thomas Erlebach and Stamatis Stefanakos: Routing to Reduce the Cost of Wavelength Conversion. Discrete Applied Mathematics 156(15):2911-2923, 2008. Available online since 21 February 2008. DOI: https://doi.org/10.1016/j.dam.2007.12.001 

• Thomas Erlebach, Alexander Hall, Alessandro Panconesi and Danica Vukadinovic: Cuts and Disjoint Paths in the Valley-Free Path Model. Internet Mathematics, 3(3):333-359, 2006-2007. https://doi.org/10.1080/15427951.2006.10129126

• Thomas Erlebach and Erik Jan van Leeuwen: Approximating Geometric Coverage Problems. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008, San Francisco, CA), pp. 1267-1276.

• Jessica Chang, Thomas Erlebach, Renars Gailis and Samir Khuller: Broadcast Scheduling: Algorithms and Complexity. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008, San Francisco, CA), pp. 473-482.

• Thomas Erlebach and Erik Jan van Leeuwen: Domination in Geometric Intersection Graphs (pdf-file). In: Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN 2008), LNCS 4957, Springer, 2008, pp. 747-758. https://doi.org/10.1007/978-3-540-78773-0_64

• Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff and Alexander Wolff: Trimming of Graphs, with Application to Point Labeling. In: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008, Bordeaux, France), pp. 265-276. https://doi.org/10.4230/LIPIcs.STACS.2008.1350

• Thomas Erlebach, Michael Hoffmann, Danny Krizanc, Matus Mihalak and Rajeev Raman: Computing Minimum Spanning Trees with Uncertainty. In: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008, Bordeaux, France), pp. 277-288. https://doi.org/10.4230/LIPIcs.STACS.2008.1358

Publications of 2007

• Leah Epstein, Thomas Erlebach, Asaf Levin: Online capacitated interval coloring. In: Proceedings of the First International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE 2007). LNCS 4614, Springer, pp. 243-254. https://doi.org/10.1007/978-3-540-74450-4_22

• Giuseppe Di Battista, Thomas Erlebach, Alexander Hall, Maurizio Patrignani, Maurizio Pizzonia, and Thomas Schank: Computing the Types of the Relationships between Autonomous Systems (pdf-file). IEEE/ACM Transactions on Networking 15(2):267-280, April 2007. http://doi.acm.org/10.1145/1279660.1279662

• Thomas Erlebach, Riko Jacob, Matus Mihalak, Marc Nunkesser, Gabor Szabo, Peter Widmayer: An algorithmic view on OVSF code assignment. Algorithmica 47(3):269-298, April 2007. Special issue on Approximation and Online Algorithms. https://doi.org/10.1007/s00453-006-0188-3

• Udo Adamy, Christoph Ambühl, R. Sai Anand, Thomas Erlebach: Call control in rings. Algorithmica 47(3):217-238, April 2007. Special issue on Approximation and Online Algorithms. https://doi.org/10.1007/s00453-006-0187-4

• Thomas Erlebach, Alexander Hall, Matus Mihalak: Approximate Discovery of Random Graphs. In: Proceedings of the 4th Symposium on Stochastic Algorithms, Foundations, and Applications (SAGA 2007). LNCS 4665, Springer, 2007, pp. 82-92. https://doi.org/10.1007/978-3-540-74871-7_8

Publications of 2006

• Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak, L. Shankar Ram: Network Discovery and Verification. IEEE Journal on Selected Areas in Communications, Vol. 24, No. 12, December 2006, pp. 2168-2181. Special issue on Sampling the Internet: Techniques and Applications. https://doi.org/10.1109/JSAC.2006.884015

• Christoph Ambühl, Thomas Erlebach, Matus Mihalak, Marc Nunkesser: Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2006), LNCS 4110, Springer, 2006, pp. 3-14.  https://doi.org/10.1007/11830924_3
  Extended version available as Research Report CS-06-008 (pdf-file), Department of Computer Science, University of Leicester, June 2006.

• Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Heiko Schilling, Martin Skutella: Length-Bounded Cuts and Flows. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), Part I. LNCS 4051, Springer, 2006, pp. 679-690.  https://doi.org/10.1007/11786986_59
  Extended version available as Preprint 005-2006, Combinatorial Optimization & Graph Algorithms Group, TU Berlin, 2006. (pdf-file)

• Leah Epstein, Thomas Erlebach, Asaf Levin: Variable Sized Online Interval Coloring with Bandwidth. In: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), LNCS 4059, Springer, 2006, pp. 29-40. https://doi.org/10.1007/11785293_6
  Extended version available as Research Report CS-06-004 (pdf-file), Department of Computer Science, University of Leicester, April 2006.

• Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak: Network Discovery and Verification with Distance Queries. In: Proceedings of the 6th Conference on Algorithms and Complexity (CIAC), LNCS 3998, Springer, 2006, pp. 69-80. https://doi.org/10.1007/11758471_10
  Extended version available as Research Report CS-06-002 (pdf-file), Department of Computer Science, University of Leicester, March 2006.

• Thomas Erlebach and Danica Vukadinovic: Path problems in generalized stars, complete graphs, and brick wall graphs. Discrete Applied Mathematics, Volume 154, Issue 4, 15 March 2006, pp. 673-683. https://doi.org/10.1016/j.dam.2005.05.017

• Thomas Erlebach: Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow (pdf-file). In E. Bampis et al. (Eds.): Efficient Approximation and Online Algorithms, LNCS 3484, Springer, 2006, pp. 97-134. https://doi.org/10.1007/11671541_4

• Thomas Erlebach and Jiri Fiala: Independence and Coloring Problems on Intersection Graphs of Disks. In E. Bampis et al. (Eds.): Efficient Approximation and Online Algorithms, LNCS 3484, Springer, 2006, pp. 135-155. https://doi.org/10.1007/11671541_5

• Thomas Erlebach, Alexander Hall, Linda Moonen, Alessandro Panconesi, Frits Spieksma and Danica Vukadinovic: Robustness of the Internet at the Topology and Routing Level. In Jürg Kohlas, Bertrand Meyer, André Schiper (Eds.): Dependable Systems: Software, Computing, Networks, LNCS 4028, Springer, 2006, pp. 260-274. https://doi.org/10.1007/11808107_12

• R. Sai Anand, Thomas Erlebach: Call Control on Lines. In: Proceedings of the First International Conference on Communication System Software and Middleware (Comsware 2006), CD-ROM, IEEE, January 2006, 6 pages. https://doi.org/10.1109/COMSWA.2006.1665178

• Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, Alexander Wolff: A New Approximation Algorithm for Labeling Weighted Points with Sliding Labels. Presented at the 22nd European Workshop on Computational Geometry (EWCG), March 27-29, 2006, Delphi, Greece. 

Publications of 2005

• Thomas Erlebach, Klaus Jansen, Eike Seidel: Polynomial-Time Approximation Schemes for Geometric Intersection Graphs. SIAM Journal on Computing, 34(6):1302-1323, 2005. https://doi.org/10.1137/S0097539702402676

• Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak, L. Shankar Ram: Network Discovery and Verification (pdf-file). In: Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), LNCS 3787, Springer, 2005, pp. 127-138. https://doi.org/10.1007/11604686_12

• Thomas Erlebach, Klaus Jansen: Conversion of Coloring Algorithms into Maximum Weight Independent Set Algorithms. Discrete Applied Mathematics, Vol. 148, No. 1, pp. 107-125, April 2005. https://doi.org/10.1016/j.dam.2004.11.007

• Thomas Erlebach, Riko Jacob, Matus Mihalak, Marc Nunkesser, Gabor Szabo, Peter Widmayer: Joint Base Station Scheduling. In: Proceedings of the Second Workshop on Approximation and Online Algorithms (WAOA 2004), Bergen, Norway, September 2004. LNCS 3351, Springer-Verlag, February 2005, pp. 225-238. https://doi.org/10.1007/978-3-540-31833-0_19
  Extended version available as Technical Report 462, Institute of Theoretical Computer Science, ETH Zürich, December 2004. https://doi.org/10.3929/ethz-a-006775343 

• Udo Adamy, Thomas Erlebach, Dieter Mitsche, Ingo Schurr, Bettina Speckmann, Emo Welzl: Off-line Admission Control for Advance Reservations in Star Networks (pdf-file). In: Proceedings of the Second Workshop on Approximation and Online Algorithms (WAOA 2004), Bergen, Norway, September 2004. LNCS 3351, Springer-Verlag, February 2005, pp. 211-224. https://doi.org/10.1007/978-3-540-31833-0_18

• Thomas Erlebach, Stamatis Stefanakos: Wavelength Conversion in All-Optical Networks with Shortest-Path Routing. Algorithmica, Vol. 43, pp. 43-61, 2005. Special Issue on Network Design. https://doi.org/10.1007/s00453-005-1157-y

• Thomas Erlebach, Alexander Hall, Alessandro Panconesi and Danica Vukadinovic: Cuts and Disjoint Paths in the Valley-Free Path Model of Internet BGP Routing. In: Proceedings of the First Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN), August 2004. LNCS 3405, Springer-Verlag, pp. 49-62, 2005. https://doi.org/10.1007/11527954_6
  Extended version available as TIK Report Nr. 180, September 2003. (pdf-file)

Publications of 2004

• Mark Cielibak, Thomas Erlebach, Fabian Hennecke, Birgitta Weber, Peter Widmayer: Scheduling with Release Times and Deadlines on a Minimum Number of Machines. In: Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science (TCS 2004), Toulouse, France, August 2004, pp. 217-230. https://doi.org/10.1007/1-4020-8141-3_18

• Hiroyuki Miyazawa and Thomas Erlebach: An Improved Randomized On-Line Algorithm for a Weighted Interval Selection Problem. Journal of Scheduling, Vol. 7, No. 4, pp. 293-311, 2004. https://doi.org/10.1023/B:JOSH.0000031423.39762.d3

• Stamatis Stefanakos and Thomas Erlebach: Routing in All-Optical Ring Networks Revisited. In: Proceedings of the 9th IEEE Symposium on Computers and Communications (ISCC 2004), pp. 288-293, 2004. https://doi.org/10.1109/ISCC.2004.1358419

• Thomas Erlebach and Alexander Hall: NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow. Journal of Scheduling, Vol. 7, pp. 223-241, 2004. https://doi.org/10.1023/B:JOSH.0000019682.75022.96

• Thomas Erlebach and Maurice Rüegg: Optimal Bandwidth Reservation in Hose-Model VPNs with Multi-Path Routing. In: IEEE Infocom, March 2004. https://doi.org/10.1109/INFCOM.2004.1354650

• Thomas Erlebach, Riko Jacob, Matus Mihalak, Marc Nunkesser, Gabor Szabo, Peter Widmayer: An Algorithmic View on OVSF Code Assignment. In: Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS 2004), Montpellier, France, March 25-27, 2004. LNCS 2996, Springer-Verlag, March 2004, pp. 270-281. https://doi.org/10.1007/978-3-540-24749-4_24
  Extended version available as TIK Report Nr. 173, August 2003. (pdf-file)

• Thomas Erlebach, Vanessa Kääb, Rolf Möhring: Scheduling AND/OR-Networks on Identical Parallel MachinesProceedings of the First Workshop on Approximation and Online Algorithms (WAOA 2003), Budapest, Hungary, September 2003. LNCS 2909, Springer-Verlag, 2004, pp. 123-136. https://doi.org/10.1007/978-3-540-24592-6_10

• Udo Adamy, Thomas Erlebach: Online Coloring of Intervals with Bandwidth. In: Proceedings of the First Workshop on Approximation and Online Algorithms (WAOA 2003), Budapest, Hungary, September 2003. LNCS 2909, Springer-Verlag, 2004, pp. 1-12. https://doi.org/10.1007/978-3-540-24592-6_1

• Mark Cieliebak, Thomas Erlebach, Zsuzsanna Lipták, Jens Stoye, Emo Welzl: Algorithmic Complexity of Protein Identification: Combinatorics of Weighted Strings. Discrete Applied Mathematics, Vol. 137, No. 1, pp. 27-46, February 2004. https://doi.org/10.1016/S0166-218X(03)00187-2

Publications of 2003

• Thomas Erlebach, Stamatis Stefanakos: Wavelength Conversion in Shortest-Path All-Optical Networks. In: Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), Kyoto, Japan, December 15-17, 2003. LNCS 2906, Springer Verlag, 2003, pp. 595-604. https://doi.org/10.1007/978-3-540-24587-2_61
  Extended version available as TIK Report Nr. 177, August 2003. (pdf-file)

• Thomas Erlebach, Aris Pagourtzis, Katerina Potika, Stamatis Stefanakos: Limited Bandwidth in Multiple-Fiber All-Optical Caterpillars: a Minimization Problem. In: Proceedings of the 1st Balkan Conference on Informatics (BCI 2003), Thessaloniki, Greece, November 21-23, 2003, pp. 133-146.

• R. Sai Anand, Thomas Erlebach: Routing and Call Control Algorithms for Ring Networks. In: Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS), Carleton Univ., Ottawa, July 30 - August 1, 2003. LNCS 2748, Springer Verlag, 2003, pp. 186-197. https://doi.org/10.1007/978-3-540-45078-8_17
  Extended version available as TIK Report Nr. 171, May 2003. (pdf-file)

• R. Sai Anand, Thomas Erlebach, Alexander Hall, Stamatis Stefanakos: Call Control with k Rejections. Journal of Computer and System Sciences, Vol. 67, pp. 707-722, December 2003. https://doi.org/10.1016/S0022-0000(03)00076-X

• Thomas Erlebach, Stamatis Stefanakos: On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements. In: Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science (STACS 2003), LNCS 2607, Springer-Verlag, February 2003, pp. 133-144.  https://doi.org/10.1007/3-540-36494-3_13
  Extended version available as TIK Report Nr. 153, October 2002. (Revised: November 14, 2002.) (pdf-file)

• Thomas Erlebach, Aris Pagourtzis, Katerina Potika, Stamatis Stefanakos: Resource Allocation Problems in Multifiber WDM Tree Networks. In: Proceedings of the 29th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2003), LNCS 2880, Springer-Verlag, 2003, pp. 218-229. https://doi.org/10.1007/978-3-540-39890-5_19
  Extended version available as TIK Report Nr. 178, August 2003. (pdf-file)

• Paz Carmi, Thomas Erlebach, Yoshio Okamoto: Greedy edge-disjoint paths in complete graphs. In: Proceedings of the 29th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2003), LNCS 2880, Springer-Verlag, 2003, pp. 143-155. https://doi.org/10.1007/978-3-540-39890-5_13
  Extended version available as TIK Report Nr. 155, February 2003. (pdf-file)

• Thomas Erlebach and Frits C.R. Spieksma: Interval selection: Applications, algorithms, and lower bounds. Journal of Algorithms, Vol. 46, No. 1, pp. 27-53, January 2003.  https://doi.org/10.1016/S0196-6774(02)00291-2
  Extended version available as TIK Report Nr. 152, October 2002. (Revised: November 28, 2002.) (pdf-file)

Publications of 2002

• Thomas Erlebach, Stamatis Stefanakos: Wavelength Conversion in Networks of Bounded Treewidth (pdf-file). TIK Report Nr. 132, April 2002.

• Thomas Erlebach and Jiri Fiala: On-line coloring of geometric intersection graphs. Computational Geometry: Theory and Applications, 23(2):243-255, August 2002. https://doi.org/10.1016/S0925-7721(02)00089-5 

• Thomas Erlebach and Alexander Hall: NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow (pdf-file). In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), 2002, pp. 194-202.
  Also: TIK Report Nr. 121, August 2001. (pdf-file)

• Thomas Erlebach, Torben Hagerup: Routing flow through a strongly connected graph. Algorithmica 32(3):467-473, 2002. https://doi.org/10.1007/s00453-001-0082-y 

• R. Sai Anand, Thomas Erlebach: On-line Algorithms for Edge-Disjoint Paths in Trees of Rings. In: Proceedings of the 5th Latin American Symposium on Theoretical Informatics (LATIN 2002), LNCS 2286, Springer-Verlag, April 2002, pp. 584-597. https://doi.org/10.1007/3-540-45995-2_50 

• Samarjit Chakraborty, Thomas Erlebach, Simon Künzli, Lothar Thiele: Schedulability of Event-Driven Code Blocks in Real-Time Embedded Systems. In: 39th Design Automation Conference (DAC 2002), June 2002. https://doi.org/10.1145/513918.514075 

• Danica Vukadinovic, Polly Huang, Thomas Erlebach: On the Spectrum and Structure of Internet Topology Graphs. In: Innovative Internet Computing Systems (I2CS 2002), LNCS 2346, Springer-Verlag, June 2002, pp. 83-95. https://doi.org/10.1007/3-540-48080-3_8 

• R. Sai Anand, Thomas Erlebach, Alexander Hall, Stamatis Stefanakos: Call Control with k Rejections. In: Proceedings of the Eighth Scandinavian Workshop on Algorithm Theory (SWAT 2002), LNCS 2368, Springer-Verlag, July 2002, pp. 308-317. https://doi.org/10.1007/3-540-45471-3_32 

• Udo Adamy, Christoph Ambühl, R. Sai Anand, Thomas Erlebach: Call Control in Rings (pdf-file). In: Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP 2002), LNCS 2380, Springer-Verlag, July 2002, pp. 788-799. https://doi.org/10.1007/3-540-45465-9_67 

• Mark Cielibak, Thomas Erlebach, Zsuzsanna Liptak, Jens Stoye, Emo Welzl: Algorithmic Complexity of Protein Identification: Searching in Weighted Strings. In: R.A. Baeza-Yates and U. Montanari, eds., Foundations of Information Technology in the Era of Networking and Mobile Computing, IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science (TCS 2002), IFIP Conference Proceedings, Vol. 223, Kluwer, 2002, pp. 143-156. https://doi.org/10.1007/978-0-387-35608-2_13 

• Thomas Erlebach: Call Admission Control for Advance Reservation Requests with Alternatives (pdf-file). In: Proceedings of the 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks (ARACNE 2002), Proceedings in Informatics, Carleton Scientific, September 2002, pp. 51-64.
  Full version: TIK Report Nr. 142, July 2002. (pdf-file)

• Thomas Erlebach, Alexander Hall and Thomas Schank: Classifying Customer-Provider Relationships in the Internet. In: Proceedings of the IASTED International Conference on Communications and Computer Networks (CCN 2002), Cambridge, USA, November 4-6, 2002, pp. 538-545.
  Full version: TIK Report Nr. 145, July 2002. (pdf-file)
  Note: Related work was done independently in the Computer Networks Research Group at University of Rome 3.

• Thomas Erlebach, Klaus Jansen: Implementation of Approximation Algorithms for Weighted and Unweighted Edge-Disjoint Paths in Bidirected Trees. ACM Journal of Experimental Algorithmics, Vol. 7, 2002. https://doi.org/10.1145/944618.944624 

• Thomas Erlebach, Hans Kellerer, and Ulrich Pferschy: Approximating Multiobjective Knapsack Problems. Management Science, 48(12):1603-1612, December 2002. https://doi.org/10.1287/mnsc.48.12.1603.445 

Older Publications of Thomas Erlebach

Publications on Network Problems

• Thomas Erlebach and Klaus Jansen: Scheduling of Virtual Connections in Fast Networks (pdf-file). In: Proceedings of the 4th Parallel Systems and Algorithms Workshop (PASA'96), World Scientific Publishing, 1997, pp. 13-32

• Thomas Erlebach and Klaus Jansen: Call Scheduling in Trees, Rings and Meshes (pdf-file). In: Proceedings of the 30th Hawaii International Conference on System Sciences (HICSS-30), Vol. 1, IEEE Computer Society Press, 1997, pp. 221-222

• Thomas Erlebach, Klaus Jansen, Christos Kaklamanis, and Pino Persiano: An Optimal Greedy Algorithm for Wavelength Allocation in Directed Tree Networks (pdf-file). In: Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location (April 28-30, 1997), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 40, American Mathematical Society, 1998, pp. 117-129

• Christos Kaklamanis, Pino Persiano, Thomas Erlebach, and Klaus Jansen: Constrained Bipartite Edge Coloring with Applications to Wavelength Routing (pdf-file). In: Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP'97), LNCS 1256, Springer Verlag, 1997, pp. 493-504

• Thomas Erlebach and Klaus Jansen: Off-line and On-line Call-Scheduling in Stars and Trees (pdf-file). In: Proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'97), LNCS 1335, Springer Verlag, 1997, pp. 199-213

• Thomas Erlebach and Klaus Jansen: Maximizing the Number of Connections in Optical Tree Networks (pdf-file). In: Proceedings of the Ninth Annual International Symposium on Algorithms and Computation (ISAAC'98), LNCS 1533, Springer Verlag, 1998, pp. 179-188.

• Thomas Erlebach and Klaus Jansen: Efficient Implementation of an Optimal Greedy Algorithm for Wavelength Allocation in Directed Tree Networks. In: Proceedings of the 2nd Workshop on Algorithm Engineering (WAE'98), Technical Report MPI-I-98-1-019, Max-Planck-Institut für Informatik, Saarbrücken, 1998, pp. 13-24.

• Thomas Erlebach: Maximum Weight Edge Disjoint Paths in Bidirected Trees. Communication and Data Management in Large Networks. Workshop of INFORMATIK'99, 1999, pp. 13-19.

• Thomas Erlebach, Klaus Jansen, Christos Kaklamanis, Milena Mihail, Pino Persiano: Optimal wavelength routing on directed fiber trees. Theoretical Computer Science (221) 1-2 (1999), pp. 119-137.

• Thomas Erlebach, Klaus Jansen: Conversion of Coloring Algorithms into Maximum Weight Independent Set Algorithms (pdf-file). In: Proceedings of the Satellite Workshops of the 27th International Colloquium on Automata, Languages, and Programming, Workshop "Approximation and Randomization Algorithms in Communication Networks" (ARACNE 2000), 2000, pp. 135-145.

• Thomas Erlebach, Klaus Jansen: Efficient Implementation of an Optimal Greedy Algorithm for Wavelength Assignment in Directed Tree Networks. ACM Journal of Experimental Algorithmics, Vol. 4, 1999.

• Thomas Erlebach and Klaus Jansen: Implementation of Approximation Algorithms for Weighted and Unweighted Edge-Disjoint Paths in Bidirected Trees. In: Proceedings of the 4th Workshop on Algorithm Engineering (WAE 2000), LNCS 1982, Springer Verlag, 2000, pp. 195-206.

• Thomas Erlebach, Klaus Jansen, Eike Seidel: Polynomial-Time Approximation Schemes for Geometric Graphs (pdf-file). In: Proceedings of the Twelth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), 2001, pp. 671-679.

• Thomas Erlebach, Klaus Jansen: The complexity of path coloring and call scheduling. Theoretical Computer Science (255) 1-2, March 2001, pp. 33-50.

• Thomas Erlebach, Klaus Jansen, Christos Kaklamanis, and Pino Persiano: Directed tree networks. In: Encyclopedia of Optimization, Volume I, Kluwer Academic Publishers, June 2001, 444-453.

• Thomas Erlebach and Danica Vukadinovic: New results for path problems in generalized stars, complete graphs, and brick wall graphs. In: Proceedings of the First International Workshop on Efficient Algorithms (WEA 2001) (in conjunction with FCT 2001), LNCS 2138, Springer Verlag, 2001, pp. 483-494.

• Thomas Erlebach: Approximation Algorithms and Complexity Results for Path Problems in Trees of Rings. In: Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001), LNCS 2136, Springer-Verlag, 2001, pp. 351-362.
  Also: TIK Report Nr. 109, August 2001. (pdf-file)

• Danica Vukadinovic, Polly Huang, Thomas Erlebach: A Spectral Analysis of the Internet Topology. TIK Report Nr. 118, July 2001. (pdf-file)

• Thomas Erlebach and Klaus Jansen: The Maximum Edge-Disjoint Paths Problem in Bidirected Trees. SIAM Journal on Discrete Mathematics, Vol. 14, No. 3, pp. 326-355, 2001.

Dissertation

• Scheduling Connections in Fast Networks (pdf-file), Technische Universität München, May 1999. 

Other Publications

• Thomas Erlebach: APERITIF - Automatic Parallelization of Divide and Conquer Algorithms. Diplomarbeit, Technische Universität München, 1994.

• Stefan Bischof and Thomas Erlebach: Classification and Survey of Strategies. In: Thomas Schnekenburger and Georg Stellner (Eds.) Dynamic Load Distribution for Parallel Applications, Teubner-Texte zur Informatik, 1997.

• Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and Thomas Zeugmann: Efficient Learning of One-Variable Pattern Languages from Positive Data. Technical Report DOI-TR-128, Department of Informatics, Kyushu University, Dec. 12, 1996

• Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and Thomas Zeugmann: Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries. In: Proceedings of the 8th International Workshop on Algorithmic Learning Theory (ALT'97), LNCS 1316, Springer Verlag, 1997, pp. 260-276.

• Stefan Bischof, Ralf Ebner and Thomas Erlebach: Load Balancing for Problems with Good Bisectors, and Applications in Finite Element Simulations. In: Proceedings of the 4th International Euro-Par Conference on Parallel Processing (EURO-PAR'98), LNCS 1470, Springer-Verlag, 1998, pp. 383-389

• Stefan Bischof, Ralf Ebner and Thomas Erlebach: Parallel Load Balancing for Problems with Good Bisectors. In: Proceedings of the 13th Merged International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP'99), IEEE, 1999, pp. 531-538.

• Ralf Ebner, Thomas Erlebach, Claudia Gold, Clemens Harlfinger, Roland Wismüller: A Framework for Recording and Visualizing Event Traces in Parallel Systems with Load Balancing. In: PASA'99 - 5. Workshop Parallele Systeme und Algorithmen, in W. Erhard et al. (Hrsg.): Workshops zur Architektur von Rechensystemen. Berichte zur Rechnerarchitektur, Universität Jena, 1999, pp. 155-162.

• Stefan Bischof, Ralf Ebner, Thomas Erlebach: Parallel Load Balancing for Problems with Good Bisectors. Journal of Parallel and Distributed Computing, Vol. 60, No. 9, pp. 1047-1073, September 2000.

• Thomas Erlebach and Frits C.R. Spieksma: Simple algorithms for a weighted interval selection problem (pdf-file). In: Eleventh Annual International Symposium on Algorithms And Computation (ISAAC 2000), LNCS 1969, Springer Verlag, 2000, pp. 228-240.

• Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and Thomas Zeugmann: Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries. Theoretical Computer Science, Vol. 261, No. 1, pp. 119-156, June 2001.

• Hiroyuki Miyaza, Thomas Erlebach: A new randomized on-line algorithm for a weighted interval selection problem. In: Workshop on Algorithms and Computation (WAAC), Pusan, Korea, June 2001.

• Thomas Erlebach, Hans Kellerer, and Ulrich Pferschy: Approximating Multi-Objective Knapsack Problems. In: Proceedings of the Seventh International Workshop on Algorithms and Data Structures (WADS 2001), LNCS 2125, Springer Verlag, 2001, pp. 210-221.

• Samarjit Chakraborty, Thomas Erlebach, and Lothar Thiele: On the Complexity of Scheduling Conditional Real-Time Code. In: Proceedings of the Seventh International Workshop on Algorithms and Data Structures (WADS 2001), LNCS 2125, Springer Verlag, 2001, pp. 38-49.
  Also: TIK Report Nr. 107, May 2001. (pdf-file)

• Mark Cieliebak, Thomas Erlebach, Zsuzsanna Lipták, Jens Stoye, Emo Welzl: Algorithmic Complexity of Protein Identification: Combinatorics of Weighted Strings. In: Combinatorics Of Searching, Sorting, And Coding (COSSAC), Ischia Island, Italy, September 2001.

• Thomas Erlebach, Martin Gantenbein, Daniel Hürlimann, Gabriele Neyer, Aris Pagourtzis, Paolo Penna, Konrad Schlude, Kathleen Steinhöfel, David Scot Taylor, and Peter Widmayer: On the complexity of train assignment problems. In: Proceedings of the Twelfth Annual International Symposium on Algorithms and Computation (ISAAC 01), Christchurch, New Zealand, December 2001. LNCS 2223, Springer Verlag, 2001, pp. 390-402.
  Also: Technical Report 363, Institute of Theoretical Computer Science, ETH Zürich, 2001. https://doi.org/10.3929/ethz-a-006654409