Theoretical Computer Science Group

Alexander Langer

E-Mail: langer@cs.rwth-aachen.de
Postal address: Alexander Langer
Lehrgebiet Theoretische Informatik
RWTH Aachen
Ahornstraße 55
52056 Aachen
Federal Republic of Germany
Phone:+49-241-80-21132
Room:6114 (Building E2)
 

Publications

Updated 2014-09-20 - see DBLP for an up-to-date list.

Journal Publications

  • Alexander Langer, Felix Reidl, Peter Rossmanith, Somnath Sikdar. Practical Algorithms for MSO Model-Checking on Tree-Decomposable Graphs. In Computer Science Review 13-14: 39-74 (2014). DOI, Preprint.
  • Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith. Digraph width measures in parameterized algorithmics. Discrete Applied Mathematics 168: 88-107 (2014). DOI, Preprint, BibTex
  • Robert Ganian, Petr Hlinený, Alexander Langer, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar. Lower bounds on the complexity of MSO1 model-checking. J. Comput. Syst. Sci. 80(1): 180-194 (2014). DOI, BibTex
  • Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith. An exact algorithm for the Maximum Leaf Spanning Tree problem. Theoretical Computer Science 412(45): 6290-6302 (2011). DOI, Preprint, BibTex
  • Joachim Kneis, Alexander Langer, Peter Rossmanith. Courcelle's Theorem - A Game-Theoretic Approach. Discrete Optimization 8(4): 568-594 (2011). DOI, Preprint, BibTeX
  • Daniel Binkele-Raible, Ljiljana Brankovic, Marek Cygan, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Marcin Pilipczuk, Peter Rossmanith, Jakub Onufry Wojtaszczyk. Breaking the 2n-barrier for Irredundance: Two lines of attack. J. Discrete Algorithms 9(3): 214-230 (2011). CIAC 2010 special issue. DOI, BibTeX
  • Joachim Kneis, Alexander Langer, Peter Rossmanith. A New Algorithm for Finding Trees with Many Leaves. Algorithmica 61(4): 882-897, 2011. ISAAC 2008 special issue. DOI, Preprint (The original publication is available at Springerlink), BibTeX

Conference Proceedings

  • Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar. Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, David Peleg (Eds.), Proc. of ICALP (1) 2013, LNCS 7965, pages 613-624. Springer, 2013. DOI, BibTeX, Full version (The original conference publication is available at Springerlink)
  • Robert Ganian, Petr Hlinený, Alexander Langer, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar. Lower Bounds on the Complexity of MSO1 Model-Checking. In Christoph Dürr, Thomas Wilke (Eds.), Proc. of STACS 2012, LIPIcs 14, pages 326-337. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012. DOI, BibTeX, PDF
  • Alexander Langer, Felix Reidl, Peter Rossmanith, Somnath Sikdar. Evaluation of an MSO-Solver. In David A. Bader, Petra Mutzel (Eds.), Proc. of ALENEX 2012, pages 55-63. SIAM / Omnipress, 2012. DOI, BibTeX, PDF
  • Alexander Langer, Peter Rossmanith, Somnath Sikdar. Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory (Extended Abstract). In Mitsunori Ogihara, Jun Tarui (Eds.), Proc. of TAMC 2011, LNCS 6648, pages 505-516. Springer, 2011. DOI, BibTeX, Preprint (The original publication is available at Springerlink), Full version
  • Ljiljana Brankovic, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith. Breaking the 2n-Barrier for Irredundance: A Parameterized Route to Solving Exact Puzzles. In Tiziana Calamoneri, Josep Diaz (Eds.), Proc. of CIAC 2010, LNCS 6078, pages 311-322. Springer, 2010. DOI, BibTeX, Preprint (The original publication is available at Springerlink)
  • Joachim Kneis, Alexander Langer, Peter Rossmanith. A Fine-grained Analysis of a Simple Independent Set Algorithm. In Ravi Kannan, K. Narayan Kumar (Eds.), Proc. of FST&TCS 2009, LIPIcs 4, pages 287-298. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2009. DOI, BibTeX, PDF
  • Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith. An Exact Algorithm for the Maximum Leaf Spanning Tree Problem. In Jianer Chen, Fedor V. Fomin (Eds.), Proc. of IWPEC 2009, LNCS 5917, pages 161-172. Springer, 2009. DOI, BibTeX, Preprint (The original publication is available at Springerlink)
  • Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith. On Digraph Width Measures in Parameterized Algorithmics. In Jianer Chen, Fedor V. Fomin (Eds.), Proc. of IWPEC 2009, LNCS 5917, pages 185-197. Springer, 2009. DOI, BibTeX, Preprint, Preprint with Appendix (The original publication is available at Springerlink)
  • Joachim Kneis, Alexander Langer. A Practical Approach to Courcelle's Theorem. In Proc. of MEMICS 2008, ENTCS Vol. 251, pages 65-81. Elsevier Science B.V., 2009. DOI, BibTeX, Preprint
  • Joachim Kneis, Alexander Langer, Peter Rossmanith. A New Algorithm for Finding Trees with Many Leaves. In S.-H. Hong, H. Nagamochi, and T. Fukunaga (Eds.), Proc. of ISAAC 2008, LNCS 5369, pages 270-281. Springer, 2008. DOI, BibTeX, Preprint (The original publication is available at Springerlink)
  • Joachim Kneis, Alexander Langer, Peter Rossmanith. Improved Upper Bounds for Partial Vertex Cover. In H. Broersma et al. (Eds.), Proc. of WG'08, LNCS 5344, pages 240-251. Springer, 2008. DOI, BibTeX, Preprint (The original publication is available at Springerlink)

Technical Reports

PhD thesis

  • Alexander Langer. Fast algorithms for decomposable graphs. RWTH Aachen University 2013, pp. 1-287. Electronic publication