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).

Program

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

Accommodation

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

Universität Tübingen	Fakultät > Wilhelm-Schickard-Institut > Paralleles Rechnen > Workshop on Cycle Bases
Arbeitsbereich Paralleles Rechnen
Startseite Program Open Problems to Work On Important Dates Accommodation Participants	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). Program 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 Accommodation 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