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 and find out who we are.

News and announcements

  • TACO 2016


    Our chair will be hosting the workshop "Treewidth And Combinatorial Optimization (TACO) 2016".

  • Sabbatical


    Prof. Rossmanith is on sabbatical leave for the winter term 2015/16. During this time there will be no fixed office hours, please contact Mrs Willms to arrange a meeting in urgent cases.

  • Abstract accepted at NETSCI 2015


    Our abstract with the title Characterizing, Predicting, and Exploiting Algorithmic Structure in Complex Networks about the results detailed in Structural Sparsity of Complex Networks: Bounded Expansion in Random Models and Real-World Graphs has been accepted at NETSCI 2015.

  • New Master Thesis Topic


    New Master Thesis on Pickup and Delivery Problems available.

  • Visitors: Pål Drange and Markus Dregi


    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


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

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


    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


    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


    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


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

  • IPEC 2011 Proceedings available


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

  • STACS and APEX '12


    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


    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


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

  • New homepage


    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.