University of Leicester

cms

HOME

MAP

CONTACT

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

Book Reviews

Publications of 2021

Publications of 2020

Publications of 2019

Publications of 2018

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.
  • 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.
  • 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.
  • 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.
  • 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.

Publications of 2016

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.
  • 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.
  • Aram Rasul, Thomas Erlebach:
    An Energy Efficient and Restricted Tour Construction for Mobile Sink in Wireless Sensor Networks
    IEEE MASS 2015, pp. 55-63.
  • 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).
  • Thomas Erlebach, Michael Hoffmann, and Frank Kammer:
    On Temporal Graph Exploration
    In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP 2015).
    LNCS 9134, Springer, 2015, pp. 444-455.
    Also: arXiv:1504.07976 [cs.DS]

Publications of 2014

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.
    The final publication is available at link.springer.com.

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.
    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.

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
  • Thomas Erlebach, Tom Grant and Frank Kammer:
    Maximising lifetime for fault-tolerant target coverage in sensor networks (pdf-file)
    In Sustainable Computing: Informatics and Systems 1(3):213-225, 2011.
  • 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.
  • Gunashekar, S.D.; Das, A.; Erlebach, T.; Warrington, E.M.: Wireless multi-hop throughput: Preliminary testbed measurements. Loughborough Antennas and Propagation Conference (LAPC), 2011. DOI: 10.1109/LAPC.2011.6114121, 2011.
  • 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. DOI: 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.

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.
  • Shagufta Henna and Thomas Erlebach: Congestion and network density adaptive broadcasting in mobile ad hoc networks. 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.
  • Shagufta Henna and Thomas Erlebach: CMAB: Cross Layer Mobility-Adaptive Broadcasting in Mobile Ad hoc Networks. 8th International Conference on Advances in Mobile Computing & Multimedia (MoMM 2010), 2010.
  • 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.
  • 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.
  • 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.
    The final publication is available at link.springer.com.
  • 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.
    The final publication is available at link.springer.com.
  • 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.
  • 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.
  • 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!).

Publications of 2009

  • Thomas Erlebach and Anna Mereu:
    Path Splicing with Guaranteed Fault Tolerance (pdf-file)
    In Proceedings of IEEE GLOBECOM 2009. IEEE, 2009.
  • 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.
    The final publication is available at link.springer.com.
  • 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.
  • Leah Epstein, Thomas Erlebach, Asaf Levin:
    Online Capacitated Interval Coloring (pdf-file)
    SIAM Journal on Discrete Mathematics 23(2):822-841, 2009.
  • 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.
  • 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.
    doi: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.
    Extended version available as Technical Report 591, Institute of Theoretical Computer Science, ETH Zürich, May 2008. (ps-file, pdf-file)
  • 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: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.
  • 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.
  • Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff and Alexander Wolff:
    Trimming of Graphs, with Application to Point Labeling (pdf-file)
    In: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008, Bordeaux, France), pp. 265-276.
  • Thomas Erlebach, Michael Hoffmann, Danny Krizanc, Matus Mihalak and Rajeev Raman:
    Computing Minimum Spanning Trees with Uncertainty (pdf-file)
    In: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008, Bordeaux, France), pp. 277-288.

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.
  • Giuseppe Di Battista, Thomas Erlebach, Alexander Hall, Maurizio Patrignani, Maurizio Pizzonia, and Thomas Schank:
    Computing the Types of the Relationships between Autonomous Systems
    IEEE/ACM Transactions on Networking 15(2):267-280, April 2007.
  • 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.
  • 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.
  • 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.

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.
  • 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.
    Extended version available as Research Report CS-06-008, Department of Computer Science, University of Leicester, June 2006. (pdf-file)
  • 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.
    Extended version available as Preprint 005-2006, Combinatorial Optimization & Graph Algorithms Group, TU Berlin, 2006.
  • 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.
    Extended version available as Research Report CS-06-004, Department of Computer Science, University of Leicester, April 2006. (pdf-file)
  • 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.
    Extended version available as Research Report CS-06-002, Department of Computer Science, University of Leicester, March 2006. (pdf-file)
  • 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.
  • Thomas Erlebach:
    Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow (pdf)
    In E. Bampis et al. (Eds.): Efficient Approximation and Online Algorithms, LNCS 3484, Springer, 2006, pp. 97-134.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Thomas Erlebach, Riko Jacob, Matus Mihalak, Marc Nunkesser, Gabor Szabo, Peter Widmayer:
    Joint Base Station Scheduling
    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.
    Extended version available as Technical Report 462, Institute of Theoretical Computer Science, ETH Zürich, December 2004. (ps-file, pdf-file)
  • Udo Adamy, Thomas Erlebach, Dieter Mitsche, Ingo Schurr, Bettina Speckmann, Emo Welzl:
    Off-line Admission Control for Advance Reservations in Star Networks (gzipped ps-file)
    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.
  • Thomas Erlebach, Stamatis Stefanakos:
    Wavelength Conversion in Shortest-Path All-Optical Networks
    Algorithmica, Vol. 43, pp. 43-61, 2005. Special Issue on Network Design.
  • Thomas Erlebach, Alexander Hall, Alessandro Panconesi and Danica Vukadinovic:
    Cuts and Disjoint Paths in the Valley-Free Path Model of Internet BGP Routing
    Proceedings of the First Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN), August 2004.
    LNCS 3405, Springer-Verlag, pp. 49-62, 2005.

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
    Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science (TCS 2004), Toulouse, France, August 2004, pp. 217-230.
  • 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.
  • Stamatis Stefanakos and Thomas Erlebach:
    Routing in All-Optical Ring Networks Revisited
    Proceedings of the 9th IEEE Symposium on Computers and Communications (ISCC 2004), pp. 288-293, 2004.
  • 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.
  • Thomas Erlebach and Maurice Rüegg:
    Optimal Bandwidth Reservation in Hose-Model VPNs with Multi-Path Routing
    IEEE Infocom, March 2004.
  • Thomas Erlebach, Riko Jacob, Matus Mihalak, Marc Nunkesser, Gabor Szabo, Peter Widmayer:
    An Algorithmic View on OVSF Code Assignment
    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.
    Extended version available as TIK Report Nr. 173, August 2003. (gzipped ps-file, pdf-file)
  • Thomas Erlebach, Vanessa Kääb, Rolf Möhring:
    Scheduling AND/OR-Networks on Identical Parallel Machines
    Proceedings of the First Workshop on Approximation and Online Algorithms (WAOA 2003), Budapest, Hungary, September 2003.
    LNCS 2909, Springer-Verlag, 2004, pp. 123-136.
  • Udo Adamy, Thomas Erlebach:
    Online Coloring of Intervals with Bandwidth
    Proceedings of the First Workshop on Approximation and Online Algorithms (WAOA 2003), Budapest, Hungary, September 2003.
    LNCS 2909, Springer-Verlag, 2004, pp. 1-12.
  • 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.

Publications of 2003

  • Thomas Erlebach, Stamatis Stefanakos:
    Wavelength Conversion in Shortest-Path All-Optical Networks
    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.
    Extended version available as TIK Report Nr. 177, August 2003. (gzipped ps-file, pdf-file)
  • Thomas Erlebach, Aris Pagourtzis, Katerina Potika, Stamatis Stefanakos:
    Limited Bandwidth in Multiple-Fiber All-Optical Caterpillars: a Minimization Problem
    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
    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.
    Extended version available as TIK Report Nr. 171, May 2003. (gzipped ps-file, 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.
  • Thomas Erlebach, Stamatis Stefanakos:
    On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements
    Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science (STACS 2003)
    LNCS 2607, Springer-Verlag, February 2003, pp. 133-144.
    Extended version available as TIK Report Nr. 153, October 2002. (Revised: November 14, 2002.) (gzipped ps-file, pdf-file)
  • Thomas Erlebach, Aris Pagourtzis, Katerina Potika, Stamatis Stefanakos:
    Resource Allocation Problems in Multifiber WDM Tree Networks
    Proceedings of the 29th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2003)
    LNCS 2880, Springer-Verlag, 2003, pp. 218-229.
    Extended version available as TIK Report Nr. 178, August 2003. (gzipped ps-file, pdf-file)
  • Paz Carmi, Thomas Erlebach, Yoshio Okamoto:
    Greedy edge-disjoint paths in complete graphs
    Proceedings of the 29th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2003)
    LNCS 2880, Springer-Verlag, 2003, pp. 143-155.
    Extended version available as TIK Report Nr. 155, February 2003 (gzipped ps-file, 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.
    Extended version available as TIK Report Nr. 152, October 2002. (Revised: November 28, 2002.) (gzipped ps-file, pdf-file)

Publications of 2002

  • Thomas Erlebach, Stamatis Stefanakos:
    Wavelength Conversion in Networks of Bounded Treewidth
    TIK Report Nr. 132, April 2002. (gzipped ps-file, pdf-file)
  • Thomas Erlebach and Jiri Fiala:
    On-line coloring of geometric intersection graphs
    Computational Geometry: Theory and Applications, 23(2):243-255, August 2002.
  • Thomas Erlebach and Alexander Hall:
    NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow (gzipped ps-file)
    Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), 2002, pp. 194-202.
    Also: TIK Report Nr. 121, August 2001. (gzipped ps-file, pdf-file)
  • Thomas Erlebach, Torben Hagerup:
    Routing flow through a strongly connected graph
    Algorithmica 32(3):467-473, 2002.
  • R. Sai Anand, Thomas Erlebach:
    On-line Algorithms for Edge-Disjoint Paths in Trees of Rings
    Proceedings of the 5th Latin American Symposium on Theoretical Informatics (LATIN 2002)
    LNCS 2286, Springer-Verlag, April 2002, pp. 584-597.
  • Samarjit Chakraborty, Thomas Erlebach, Simon Künzli, Lothar Thiele:
    Schedulability of Event-Driven Code Blocks in Real-Time Embedded Systems
    39th Design Automation Conference (DAC 2002), June 2002.
  • Danica Vukadinovic, Polly Huang, Thomas Erlebach:
    On the Spectrum and Structure of Internet Topology Graphs
    Innovative Internet Computing Systems (I2CS 2002)
    LNCS 2346, Springer-Verlag, June 2002, pp. 83-95.
  • R. Sai Anand, Thomas Erlebach, Alexander Hall, Stamatis Stefanakos:
    Call Control with k Rejections
    Proceedings of the Eighth Scandinavian Workshop on Algorithm Theory (SWAT 2002)
    LNCS 2368, Springer-Verlag, July 2002, pp. 308-317.
  • Udo Adamy, Christoph Ambühl, R. Sai Anand, Thomas Erlebach:
    Call Control in Rings (gzipped ps-file)
    Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP 2002)
    LNCS 2380, Springer-Verlag, July 2002, pp. 788-799.
  • 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.
  • Thomas Erlebach:
    Call Admission Control for Advance Reservation Requests with Alternatives (gzipped ps-file)
    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. (gzipped ps-file, pdf-file)
  • Thomas Erlebach, Alexander Hall and Thomas Schank:
    Classifying Customer-Provider Relationships in the Internet
    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. (gzipped ps-file, 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.
  • Thomas Erlebach, Hans Kellerer, and Ulrich Pferschy:
    Approximating Multiobjective Knapsack Problems
    Management Science, 48(12):1603-1612, December 2002.

Older Publications of Thomas Erlebach

Publications on Network Problems

  • Thomas Erlebach and Klaus Jansen
    Scheduling of Virtual Connections in Fast Networks (gzipped ps-file)
    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 (gzipped ps-file)
    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 (gzipped ps-file)
    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 (gzipped ps-file)
    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 (gzipped ps-file)
    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 (gzipped ps-file)
    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 (gzipped ps-file)
    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 (gzipped ps-file)
    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
    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 (gzipped ps-file)
    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
    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
    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. (gzipped ps-file, 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

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
    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
    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
    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
    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
    Eleventh Annual International Symposium on Algorithms And Computation (ISAAC 2000) (gzipped ps-file)
    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
    Workshop on Algorithms and Computation (WAAC), Pusan, Korea, June 2001.
  • Thomas Erlebach, Hans Kellerer, and Ulrich Pferschy:
    Approximating Multi-Objective Knapsack Problems
    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
    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. (gzipped ps-file)
  • Mark Cieliebak, Thomas Erlebach, Zsuzsanna Lipták, Jens Stoye, Emo Welzl:
    Algorithmic Complexity of Protein Identification: Combinatorics of Weighted Strings
    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
    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, ETH Zürich, 2001.

Author: Thomas Erlebach (t.erlebach at mcs dot le dot ac dot uk).
© University of Leicester 21st September 2004. Last modified: 31st August 2021, 11:10:14
CMS Web Maintainer. Any opinions expressed on this page are those of the author.