WG 2003 29th Workshop on Graph Theoretic Concepts in Computer Science

Home - Aims and Scope - Call for Papers - Program - Workshop Venue - Program and Organization Committees - Registration - Past and future workshops - Photo's - Proceedings

Program WG 2003

18.00 Reception and meal

The registration desk is open on Wednesday, June 18, from 17.00 till 20.30.

8.50  Opening of the workshop

9.00  Vida Dujmovic and David R. Wood

Tree-partitions of k-trees with applications in graph layout.

9.25  Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Stephen Wismath

Drawing planar graphs on a curve

9.50  Luerbio Faria, Celina M. H. de Figueiredo, Ondrej Sýkora, and Imrich Vrto

An improved upper bound on the crossing number of the hypercube

10.15  Sabine Cornelsen and Dorothea Wagner

Completely connected clustered graphs

10.40  Coffee and tea break

11.00  Simon M. Becker and Bernhard Westfechtel

Incremental integration tools for chemical engineering: An industrial application of triple graph grammars

11.25  Thomas Erlebach, Aris Pagourtzis, Katerina Potika, and Stamatis Stefanakos

Resource allocation problems in multifiber WDM Tree networks

11.50  Christian Collberg, Stephen Kobourov, Edward Carter, and Clark Thomborson

Error-correcting graphs for software watermarking

12.15  Lunch

13.45  Alexander Schrijver CWI, Amsterdam, the Netherlands

Invited Lecture: Matching, colouring, scheduling, and dimers

14.35  Pascal Berthomé, Madiagne Diallo, and Afonso Ferreira

Generalized parametric multi-terminal flow problem

15.00  Paz Carmi, Thomas Erlebach, and Yoshio Okamoto

Greedy edge-disjoint paths in complete graphs

15.25  Coffee and tea break

15.45  Anna Bretscher, Derek Corneil, Michel Habib, and Christophe Paul

A simple linear time LexBFS cograph recognition algorithm

16.10  Martin C. Golumbic and Marina Lipshteyn

Chordal probe graphs

16.35  Ton Kloks, C.M. Lee, Jiping Liu, and Haiko Müller

On the recognition of general partition graphs

17.00  Stavros D. Nikolopoulos and Leonidas Palios

Recognizing bipolarizable and P₄-simplicial graphs

18.00  Dinner

9.00  Claudio Arbib, Michele Flammini, Fabrizio Marinelli

Minimum flow time graph ordering

9.25  Ioan Todinca

Coloring powers of graphs of bounded clique-width

9.50  Alexander Glikson and Johann A. Makowsky

NCE graph grammars and clique-width

10.15  Dieter Kratsch, Haiko Müller, and Ioan Todinca

Feedback vertex set and longest induced path on AT-free graphs

10.40  Coffee and tea break

11.00  Lali Barrière, Pierre Fraigniaud, Nicola Santoro, and Dimitrios M. Thilikos

Searching is not jumping

11.25  Anne Berry, Pinar Heggernes, and Geneviève Simonet

The Minimum Degree heuristic and the minimal triangulation process

11.50  Asaf Levin, Daniel Paulusma, and Gerhard J. Woeginger

The complexity of graph contractions

12.15  Frank Dehne, Michael R. Fellows, and Frances A. Rosamond

An FPT algorithm for Set Splitting

12.40  Lunch

14.00  Excursion

In the excursion, the participants will visit the nearby National Park De Hoge Veluwe. During the excursion, the participants will have the possibilities to use a bike through the park and/or to visit the Kröller-Müller Museum with many famous paintings and sculptures, including a special exhibition of paintings of Vincent van Gogh.

• Website of De Hoge Veluwe.
• Website of the Kröller-Müller Museum.

18.30  Conference dinner

9.00  Michael R. Fellows, University of Newcastle, Australia

Invited lecture: Blow-ups, win/win's and crown rules: some new directions in FPT graph algorithms

9.50  A. Brandstädt, F.F. Dragan, H.-O. Le, V.B. Le, and R. Uehara

Tree spanners for bipartite graphs and probe interval graphs

10.15  Paul Manuel, Bharati Rajan, Indra Rajasingh, and Amutha Alaguvel

Tree spanners, Cayley graphs and diametrically uniform graphs

10.40  Coffee and tea break

11.00  Hajo Broersma, Fedor V. Fomin, Petr A. Golovach, and Gerhard J. Woeginger

Backbone colorings for networks

11.25  Cécile Murat and Vangelis Th. Paschos

The probabilistic minimum coloring problem

11.50  Jan Kratochvíl

Complexity of hypergraph coloring and Seidel's switching

12.15  Lunch

13.45  Paul Bonsma

The complexity of the matching-cut problem for planar graphs and other graph classes

14.10  Lukasz Kowalik

Short cycles in planar graphs

14.35  Carsten Gutwenger, Michael Jünger, Sebastian Leipert, Petra Mutzel, Mirijam Percan, and René Weiskircher

Subgraph induced planar connectivity augmentation

15.00  Nicolas Bonichon, Cyril Gavoille, and Nicolas Hanusse

Canonical decomposition of outerplanar maps and application to enumeration, coding and generation

15.25  End of workshop