Universität Tübingen Fakultät > Wilhelm-Schickard-Institut > Paralleles Rechnen > Workshop on Cycle Bases
Arbeitsbereich Paralleles Rechnen

Workshop on Cycle and Cut Bases

Although cycle bases were already introduced by Kirchhoff, the mathematics to analyze and the algorithms to compute them are still hot topics. A related but different topic are so-called cut bases of graphs that denote a nearly unknown territory. Together with Christian Liebchen (TU Berlin) and Horst Hamacher (Kaiserslautern) we thus invite you to this workshop to work on open problems in both realms and to find out where the similarities and differences between cycle and cut bases are. The workshop is organized within the framework of the SPP 1126 (Algorithmik großer und komplexer Netzwerke).


This workshop will be a meeting point for those groups and scientists that have already worked on either topic. We will meet on Wednesday, the 14th of May, 2008, 16:30h and use the first evening to present some open problems in the realm of the two topics. The plan is that the organizers will provide three open problems and that we will additionally accept one or two open problems from other participants. The next two days of the workshop are dedicated to work on the open problems. The results obtained so far will then be summarized on Friday, the 16th of May 2008.

Open Problems

We have not definitely decided which kind of open problems we will work on, but here are some possibilities:

  • The minimal length of a cycle basis (MCB) was shown to be in O(m log n) (Rizzi, 07). Is there a graph family where the length of an MCB is in Ω (m log n) and where m is in ω(n)?
  • The best known upper bound for the length of strictly fundamental cycle bases is O(m log^2 n loglog n) for unweighted graphs (Elkin, Emek, Spielmann, Teng, 2005). Is there any better upper bound, e.g., in planar graphs??
  • What is the structure of Nash Equilibria in a cooperative game for constructing cut bases?

Important Dates

The group should not be larger than 20 people to make the workshop efficient. We will thus accept applications on a first-come-first-serve manner.

  • Deadline: 28.2.2008 Please contact Katharina Zweig at "lehmannk AT informatik.uni-tuebingen.de"
  • Workshop: 14.5.2008, 16:30 h - 16.5.2008, 18 h
  • Social Event: 14.5.2008, 19h


Since the hotel Meteora seems to be fully booked, we recommend the nice and very convenient Hotel Garni Sand.

Participants (as of 18.1.2008)

  • University of Udine:
    • Romeo Rizzi (invited speaker)
  • Universität Tübingen:
    • Michael Kaufmann
    • Katharina Zweig
    • Markus Geyer
    • Volker Menrad
  • Universität Kaiserslautern:
    • Horst W. Hamacher
    • Anne Schwahn
    • Florentine Bunke
  • Technische Universität Berlin:
    • Christian Liebchen
    • Torsten Ueckert
  • University of Leipzig:
    • Peter F. Stadler
    • Konstantin Klemm
  • University of Konstanz
    • Sabine Cornelsen
  • Institut National de Recherche en Informatique et en Automatique
    • Dimitris Michail
  • Brandenburg Technische Universität Kottbus
    • Alexander Reich

Anregungen / Kritik Impressum minicms