Welcome to the Theory Group

We specialize in exact and parameterized algorithms for NP-hard problems. On this web presence you can view our current and past teaching activities, our research areas including our publications and of course find out who we are.

News and announcements

  • Visitors: Pål Drange and Markus Dregi

    17.09.2014

    We are happy to receive Pål Drange and Markus Dregi from Bergen University as our guests.

  • Talk by Blair D. Sullivan

    07.08.2014 at 10:30am

    We invite everyone to attend her talk Bringing Theory to the Real World: is structural sparsity realistic? on Thursday 7th, 10:30 in Room E3-9220 in the Informatik building.

    Abstract: Analysis and visualization of massive graphs is currently accomplished via a hodgepodge of ad hoc, often heuristic, methodologies across disciplines, as more rigorous approaches fail to scale (due to high computational complexity and lack of data locality). On the other hand, the theoretical community has long known that graph structure can have a huge impact on algorithmic complexity - in fact, this is one of the primary tenets of fixed parameter tractability (FPT). Unfortunately, direct application of results from parameterized complexity is typically infeasible due to (1) large hidden constants in the time or memory complexity and (2) the fragility of existing graph parameters to small perturbations in the network connectivity. In this talk, we discuss initial work looking at how real-world networks might fit into broader classes in the hierarchy (bounded expansion/degeneracy), including algorithmic advances and empirical evaluations. As time permits, we will discuss connections to social networks and the connectome (brain networks).

  • Visitors: Ling-Ju Hung and Blair D. Sullivan

    04.08.2014

    We are happy to receive both Ling-Ju Hung of the HKU and Blair D. Sullivan of the NCSU as our guests!

  • ICALP 2014

    14.07.2014

    Fernando presented our paper “A Faster Parameterized Algorithm for Treedepth” at ICALP 2014 in an unusually warm Copenhagen.

  • Click here to view older news
  • Visitor: Blair D. Sullivan

    10.12.2013

    We are happy to receive Blair D. Sullivan of the NCSU as our guest! We invite everyone to attend her talk Is Intermediate-Scale Structure Tree-like in Social Networks? on Thursday 12th, 16:00 in Room E3-009 in the Informatik building.

  • Visitor: Pål Grønås Drange

    4.11.2013

    From November 5th to November 16th we will have Pål Grønås Drange from the Bergen Computer Science group as a visitor.

  • New page: thesis proposals

    13.09.2012

    We remodeled our page with current topics for bachelor/master/diploma theses. If you are interested in writing about one of the proposed topics or if you have an idea of your own, contact us!

  • Dagstuhl Seminar on Data Reduction and Problem Kernels

    10.06.12-15.06.12

    Our group attended the very successful seminar on kernelization at Dagstuhl.

  • IPEC 2011 Proceedings available

    15.03.2012

    The online proceedings of IPEC 2011 are now availabe at Springer online as LNCS volume 7112

  • STACS and APEX '12

    17.02.2012

    Our group will visit STACS '12 and present the paper Lower Bounds on the Complexity of MSO1 Model Checking. Additionally, during the co-located workshop APEX '12, we will talk about Linear Kernels for Problems in Graphs Excluding a Topological Minor.

  • TACO Day '12

    19.01.2012

    Our group will attend the workshop on Treewidth and Combinatorial Optimization (TACO '12) in Maastricht on February 1st. The members of our group will give talks on the following topics: Lower Bounds on the Complexity of MSO1 Model Checking and Linear Kernels for Problems in Graphs Excluding a Topological Minor.

  • Upcoming lectures and seminars

    10.01.2012

    For the summer term 2012 we will offer a Masters course on Analysis of Algorithms and a seminar on Kompressionsalgorithmen (in German).

  • New homepage

    05.12.2011

    We finally made the switch to our new homepage. If any links should be unreachable or other errors occur, please contact Felix Reidl.

  • Sabbatical in WS 2010/2011

    Prof. Rossmanith is on a sabbatical (vorlesungsfreies Forschungssemester) in the winter term 2010/2011. Hence, there will be no scheduled office hours (Sprechstunden) during WS 2010/2011.

    For appointments with Prof. Rossmanith, please consult Mrs. Birgit Willms (please state reason for and content of the appointment).

  • TACO-day 2010

    The TACO DAY June'10 will take place in Aachen at June, 10th.