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
Talk by Blair D. Sullivan07.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. Sullivan04.08.2014
Visitor: Blair D. Sullivan10.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 Drange4.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 proposals13.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 Kernels10.06.12-15.06.12
Our group attended the very successful seminar on kernelization at Dagstuhl.
IPEC 2011 Proceedings available15.03.2012
- Click here to view older news
STACS and APEX '1217.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 '1219.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 seminars10.01.2012
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).
The TACO DAY June'10 will take place in Aachen at June, 10th.