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.
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.
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.
C. Mommessin, T. Erlebach and N.V. Shakhlevich, Classification and evaluation of the algorithms for vector bin packing. Computers and Operations Research, Volume 173, January 2025, 106860. https://doi.org/10.1016/j.cor.2024.106860
Thomas Erlebach, Nils Morawietz, Petra Wolf: Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization. Theoretical Computer Science, Volume 1051, 9 October 2025, 115412 (part of special issue with invited papers from SAND 2024). https://doi.org/10.1016/j.tcs.2025.115412
Thomas Erlebach, Othon Michail and Nils Morawietz: Recognizing and Realizing Temporal Reachability Graphs. In: 33rd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 93:1-93:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025). https://doi.org/10.4230/LIPIcs.ESA.2025.93
Also: https://arxiv.org/abs/2503.15771 [cs.CC]
Thomas Erlebach, Naveen Garg, Sukriti Gupta and Amitabh Trehan: Approximating Optimal Broadcast of Files in a Hose-Model Network. In: 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). To appear.
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]
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
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
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
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]
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
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]
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
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
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]
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
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.
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
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
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
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
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
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
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.
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)
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
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)
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
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.
Scheduling Connections in Fast Networks (pdf-file), Technische Universität München, May 1999.
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