Thomas Erlebach's Publications

Edited Books and Special Issues

• 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.
  Available from SpringerLink: Click here
• Thomas Erlebach and Christos Kaklamanis (Eds.):
  Proceedings of the 4th Workshop on Approximation and Online Algorithms (WAOA 2006)
  LNCS 4368, Springer Verlag, 2006.
  Available from SpringerLink: Click here
• Yossi Azar and Thomas Erlebach (Eds.):
  Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006)
  LNCS 4168, Springer Verlag, 2006.
• Thomas Erlebach (Ed.):
  Proceedings of the Third Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN 2006)
  LNCS 4235, Springer Verlag, 2006.
• Thomas Erlebach and Giuseppe Persiano (Eds.):
  Proceedings of the Third Workshop on Approximation and Online Algorithms (WAOA 2005)
  LNCS 3879, Springer Verlag, 2006.
• Ulrik Brandes and Thomas Erlebach (Eds.):
  Network Analysis - Methodological Foundations
  LNCS Tutorial 3418, Springer Verlag, 2005.

Book Reviews

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

Publications of 2011

• Thomas Erlebach, Tom Grant and Frank Kammer:
  Maximising lifetime for fault-tolerant target coverage in sensor networks
  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
  In Sustainable Computing: Informatics and Systems 1(3):213-225, 2011.
• Jessica Chang, Thomas Erlebach, Renars Gailis and Samir Khuller:
  Broadcast Scheduling: Algorithms and Complexity
  ACM Transactions on Algorithms 7(4), 2011.

Publications of 2010

• Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondrej Pangrac, Heiko Schilling, Martin Skutella:
  Length-Bounded Cuts and Flows
  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
  In Proceedings of the 18th IEEE International Conference on Network Protocols (ICNP 2010), IEEE, 2010. To appear.
• Thomas Erlebach and Erik Jan van Leeuwen:
  PTAS for Weighted Set Cover on Unit Squares
  In Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010), LNCS 6302, Springer-Verlag, 2010, pp. 166-177.
• Thomas Erlebach and Tom Grant:
  Scheduling Multicast Transmissions Under SINR Constraints
  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.
• Ambreen Shahnaz and Thomas Erlebach:
  Approximating fault-tolerant Steiner subgraphs in heterogeneous wireless networks.
  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
  Theoretical Computer Science 411(14-15):1626-1637, 2010. SIROCCO 2008 special issue.

Publications of 2009

• Thomas Erlebach and Anna Mereu:
  Path Splicing with Guaranteed Fault Tolerance
  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
  In Proceedings of the 7th Workshop on Approximation and Online Algorithms (WAOA 2009). LNCS 5893, Springer-Verlag, 2010, pp. 135-146.
  
• Thomas Erlebach and Ambreen Shahnaz:
  Approximating Node-Weighted Multicast Trees in Wireless Ad-Hoc Networks
  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
  SIAM Journal on Discrete Mathematics 23(2):822-841, 2009.
• Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff and Alexander Wolff:
  Trimming of Graphs, with Application to Point Labeling
  Theory of Computing Systems 47(3):613-636, 2010. STACS 2008 special issue. Published online February 2009 (Open Access!).
• Thomas Erlebach, Linda Moonen, Frits Spieksma and Danica Vukadinovic:
  Connectivity Measures for Internet Topologies
  Operations Research 57(4):1006-1025, July-August 2009.
• Leah Epstein, Thomas Erlebach, Asaf Levin:
  Variable Sized Online Interval Coloring with Bandwidth
  Algorithmica 53(3):385-401, 2009. Available online since 13 October 2007.
  doi:10.1007/s00453-007-9071-0

Publications of 2008

• 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
  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 (I²CS 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

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

Other Publications

• Thomas Erlebach
  APERITIF - Automatic Parallelization of Divide and Conquer Algorithms
  Diplomarbeit, Technische Universität München, 1994.
• Stefan Bischof and Thomas Erlebach
  Classification and Survey of Strategies
  In: Thomas Schnekenburger and Georg Stellner (Eds.) Dynamic Load Distribution for Parallel Applications, Teubner-Texte zur Informatik, 1997.
  
• Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and Thomas Zeugmann
  Efficient Learning of One-Variable Pattern Languages from Positive Data
  Technical Report DOI-TR-128, Department of Informatics, Kyushu University, Dec. 12, 1996
• Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and Thomas Zeugmann
  Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries
  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: 4th December 2011, 14:51:09.
CS Web Maintainer. Any opinions expressed on this page are those of the author.