> Friedrich-Schiller-Universität Jena
Fakultät für Mathematik und Informatik
Theoretische Informatik I
> Research/Project ITKO

DFG Project ITKO: Iterative Compression for Solving Hard Network Problems

Project ITKO (DFG Project NI 369/5) is part of the DFG-Schwerpunkt 1126 “Algorithms on large and complex networks”.

Project Description

The technique of “iterative compression” recently suggested by Reed, Smith, and Vetta provides a new tool for the design of exact algorithms for combinatorial complex network problems. The project ITKO aims to investigate the theoretical foundations of iterative compression and to explore and extend its range of application. In particular the (improved) method is to be applied to a list of concretely suggested network problems to obtain new efficient algorithms. Last but not least an objective is to implement and and test the thus gained algorithms in a practical environment. First experiences of the working group in handling iterative compression are very promising.

People

Photo of Hannes Moser Hannes Moser
Dipl.-Inform., Researcher
Room 3323
Phone: (+49) 3641 9 46324

Head: Rolf Niedermeier
Associated:

Publications

Software

  • The Balanced Subgraph solver “bsg” based on iterative compression.

Related Work of the Group

Publications

Software

  • The Graph Bipartization solver “occ” based on iterative compression.
Valid HTML 4.01! Last modified: Wed Feb 18 12:03:48 CET 2009