Institut für Theoretische Informatik, Algorithmik

Veröffentlichungen

Buchbeiträge

  1. Multi-scale Anchor-free Distributed Positioning in Sensor Networks.
    In: Sensor and Ad-Hoc Networks: Theoretical and Algorithmic Aspects, volume 7 of Lecture Notes in Electrical Engineering, pages 203–220. Springer, October 2008.
    Joint work with Dorothea Wagner.
    [ html ]

Artikel in Zeitschriften

  1. The Density Maximization Problem in Graphs.
    Journal of Combinatorial Optimization, 26(4):723–754, 2013.
    Special issue of COCOON'11.
    Joint work with Mong-Jen Kao, Marcus Krug, Der-Tsai Lee, Ignaz Rutter, and Dorothea Wagner.
    [ html ]
  2. Parallel Computation of Best Connections in Public Transportation Networks.
    ACM Journal of Experimental Algorithmics, 17(4):4.1–4.26, July 2012.
    Joint work with Daniel Delling and Thomas Pajor.
    [ html ]
  3. An algorithmic study of switch graphs.
    Acta Informatica, 49(5):295–312, 2012.
    Joint work with Ignaz Rutter and Gerhard J. Woeginger.
    [ pdf ]

Artikel in Tagungsbänden

  1. Connecting Two Trees with Optimal Routing Cost.
    In: Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG '11), pages 43–47. University of Toronto Press, 2011.
    Joint work with Mong-Jen Kao, Marcus Krug, Der-Tsai Lee, Martin Nöllenburg, Ignaz Rutter, and Dorothea Wagner.
    [ html | pdf ]
  2. The Density Maximization Problem in Graphs.
    In: Proceedings of the 17th Annual International Conference on Computing Combinatorics (COCOON'11), volume 6842 of Lecture Notes in Computer Science, pages 25–36. Springer, 2011.
    Joint work with Mong-Jen Kao, Marcus Krug, Der-Tsai Lee, Ignaz Rutter, and Dorothea Wagner.
  3. Speed Dating: An Algorithmic Case Study Involving Matching and Scheduling.
    In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 292–303. Springer, 2011.
    Joint work with Ignaz Rutter, Ben Strasser, and Dorothea Wagner.
  4. Gateway Decompositions for Constrained Reachability Problems.
    In: Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), volume 6049 of Lecture Notes in Computer Science, pages 449–461. Springer, May 2010.
    Joint work with Marcus Krug, Andreas Lochbihler, Ignaz Rutter, Gregor Snelting, and Dorothea Wagner.
  5. Preprocessing Speed-Up Techniques is Hard.
    In: Proceedings of the 7th Conference on Algorithms and Complexity (CIAC'10), volume 6078 of Lecture Notes in Computer Science, pages 359–370. Springer, 2010.
    Joint work with Reinhard Bauer, Tobias Columbus, Marcus Krug, and Dorothea Wagner.
    [ pdf ]
  6. Multi-Scale Dead-Reckoning Algorithm for Distributed Force-Directed Sensor Network Localization.
    In: Proceedings of the 6th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS'10), Lecture Notes in Computer Science, 2010.
    Joint work with Kevin Coogan, Varun Khare, and Stephen G. Kobourov.
  7. Parallel Computation of Best Connections in Public Transportation Networks.
    In: 24th International Parallel and Distributed Processing Symposium (IPDPS'10), pages 1–12. IEEE Computer Society, 2010.
    Joint work with Daniel Delling and Thomas Pajor.
    [ pdf ]
  8. Manhattan-Geodesic Embedding of Planar Graphs.
    In: Proceedings of the 17th International Symposium on Graph Drawing (GD'09), volume 5849 of Lecture Notes in Computer Science, pages 207–218. Springer, 2010.
    Joint work with Marcus Krug, Ignaz Rutter, and Alexander Wolff.
    [ html ]
  9. Energy Efficient Scheduling with Power Control for Wireless Networks.
    In: Proceedings of the 8th Intl. Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt'10), pages 144–153. IEEE Computer Society, 2010.
    Joint work with Markus Völker and Dorothea Wagner.
    [ html | pdf ]
  10. An Algorithmic Study of Switch Graphs.
    In: Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'09), volume 5911 of Lecture Notes in Computer Science, pages 226–237. Springer, June 2009.
    Joint work with Ignaz Rutter and Gerhard J. Woeginger.
    [ html ]
  11. Efficient Scheduling of Data Harvesting Trees.
    In: Proceedings of the 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS'08), volume 5389 of Lecture Notes in Computer Science, pages 43–56, 2008.
    Joint work with Steffen Mecke and Dorothea Wagner.
    [ html | pdf ]
  12. Link Scheduling in Local Interference Models.
    In: Proceedings of the 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS'08), volume 5389 of Lecture Notes in Computer Science, pages 57–71, 2008.
    Joint work with Markus Völker and Dorothea Wagner.
    [ html | pdf ]
  13. Maximum Rigid Components as Means for Direction-Based Localization in Sensor Networks.
    In: Proceedings of the 33rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'07), volume 4362 of Lecture Notes in Computer Science, pages 330–341. Springer, January 2007.
    Joint work with Marco Gaertler and Dorothea Wagner.
    [ html | pdf ]
  14. Multi-scale Anchor-free Distributed Positioning in Sensor Networks.
    In: Proceedings of the International Workshop on Theoretical and Algorithmic Aspects of Sensor Networks (WTASA'07), pages 64–74, 2007.
    Joint work with Dorothea Wagner.
    [ pdf ]

Dissertation

  1. Positioning and Scheduling of Wireless Sensor Networks — Models, Complexity, and Scalable Algorithms .
    PhD thesis, Universität Karlsruhe (TH), Fakultät für Informatik, January 2009.
    [ html | pdf ]

Technische Berichte

  1. The Density Maximization Problem in Graphs.
    Technical Report 2011-18, ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT), 2011.
    Joint work with Ming-Yang Kao, Marcus Krug, Der-Tsai Lee, Ignaz Rutter, and Dorothea Wagner.
    [ html ]
  2. Preprocessing Speed-Up Techniques is Hard.
    Technical Report 2010-04, ITI Wagner, Faculty of Informatics, Karlsruhe Institute of Technology, 2010.
    Joint work with Reinhard Bauer, Tobias Columbus, Marcus Krug, and Dorothea Wagner.
    [ html ]
  3. Parallel Computation of Best Connections in Public Transportation Networks.
    Technical Report 2009-16, Faculty of Informatics, Karlsruhe Institute of Technology, 2009.
    Joint work with Daniel Delling and Thomas Pajor.
    [ pdf ]
  4. Manhattan-Geodesic Point-Set Embeddability and Polygonization .
    Technical Report 2009-17, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2009.
    Joint work with Marcus Krug, Ignaz Rutter, and Alexander Wolff.
    [ html | pdf ]
  5. On the Complexity of Scheduling with Power Control in Geometric SINR.
    Technical Report 2009-15, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2009.
    Joint work with Markus Völker and Dorothea Wagner.
    [ html | pdf ]
  6. Maximum Rigid Components as Means for Direction-Based Localization in Sensor Networks.
    Technical Report 2006-17, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2006.
    Joint work with Marco Gaertler and Dorothea Wagner.
    [ html | pdf ]