Program

Monday, June 21st
8.50Opening (J. Hromkovic)
9.00Invited Speaker - Derek G. Corneil:Graph Searching with Emphasis on Lexicographic Breadth First Search
9.50Hans Bodlaender, Arie Koster:On the Maximum Cardinality Search Lower Bound for Treewidth
10.15Shin-ichi Nakano, Takeaki Uno:Constant Time Generation of Trees with Specified Diameter
10.40Coffee & Tea
11.00Gabriele Di Stefano, Sabine Cornelsen:Treelike Graphs: Characterization, Recognition, and Applications
11.25Jiri Fiala, Peter Golovach, Jan Kratochvil:Elegant distance constrained labelings of trees
11.50Christophe Paul, Christophe Crespelle:Fully-dynamic recognition algorithm and certificate for directed cographs
12.15Stavros Nikolopoulos, Leonidas Palios:Recognizing HHD-free and Welsh-Powell Opposition Graphs
12.40Lunch
14.10Fabien de Montgolfier, Jean-Luc Fouquet, Michel Habib, Jean-Marie Vanherpe:Bimodular decomposition of bipartite graphs
14.35Michaël Rao:Coloring a graph using split decomposition
15.00Fabrizio Grandoni, Giuseppe F. Italiano:Decremental Clique Problem
15.25Coffee & Tea
15.45Daniel Sawitzki:A Symbolic Approach to the All-Pairs Shortest-Paths Problem
16.10Mordecai Golin, Yiu Cho Leung:Unhooking Circulant Graphs
16.35Eduardo Moreno, Martin Matamala:Minimal de Bruijn Sequence in a Language with Forbidden Substrings
17.00Franz Baader:A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept
18.00Dinner
Tuesday, June 22nd
9.00Massimiliano Caramia, Nicola Apollonio, Giuseppe F. Italiano:A Stochastic Location Problem with Applications to Tele-Diagnostic
9.25Tim Nieberg, Johann Hurink, Walter Kern:A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs
9.50Christian Sloper, Mike Fellows, Pinar Heggernes, Frances Rosamond, Jan Arne Telle:Finding k disjoint triangles in an arbitrary graph
10.15Fedor Fomin, Dieter Kratsch, Gerhard Woeginger:Exact (exponential) algorithms for the dominating set problem
10.40Coffee & Tea
11.00David Juedes, Benny Chor, Mike Fellows:Linear Kernels in Linear Time, or How to Save k Colors in O(n^2) steps
11.25Cyril Gavoille, Bonichon N., Hanusse N., Poulalhon D., Schaeffer G.:Planar Graphs, via Well-Orderly Maps and Trees
11.50Valentin Brimkov, Reneta Barneva, Reinhard Klette, Joseph Straight:Lovasz theta-function of a class of graphs representing digital lines
12.15Boris Goldengorin, Marcel Turkensteen:What is the best branching rule for the ATSP?
12.40Lunch
14.00Social Event
  • Rhine Cruise from Bad Honnef to Bonn
  • Visit of the Haus der Deutschen Geschichte (History of the Federal Republic of Germany)
  • Visit of the Beethovenhaus (Beethoven's birth place)
  • Barbecue in the Park of the Conference Location
  • Wine Tasting
Wednesday, June 23rd
9.00Invited Speaker - Roger Wattenhofer:Wireless Networking: Graph Theory Unplugged
9.50Daniel Paulusma, H.J. Broersma, G.J.M. Smit, F. Vlaardingerbroek, G.J. Woeginger:The computational complexity of the minimum weight processor assignment problem
10.15Zhi-Zhong Chen, Tatsuie Tsukiji:Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs
10.40Coffee & Tea
11.00Md. Saidur Rahman, Kazuyuki Miura, Takao Nishizeki:Octagonal Drawings of Plane Graphs with Prescribed Face Areas
11.25Michael Baur, Ulrik Brandes:Crossing Reduction in Circular Layouts
11.50Jayme Szwarcfiter, Mitre C Dourado, Fabio Protti:Characterization and recognition of generalized clique-Helly graphs
12.15Guido Proietti, Michele Conforti, Anna Galluccio:Edge-connectivity augmentation and network matrices
12.40Lunch
14.10Takehiro Ito, Xiao Zhou, Takao Nishizeki:Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size
14.35Jerome Monnot, Dominique de Werra, Marc Demange, Vangelis Th. Paschos:The hypocoloring problem:complexity and approximability results when the chromatic number is small
15.00Yoshio Okamoto, Thomas Bietenhader:Core Stability of Minimum Coloring Games
15.25Feodor F. Dragan, Chenyu Yan, Derek G. Corneil:Collective Tree Spanners and Routing in AT-free Related Graphs
15.50Closing Remarks (M. Nagl)
16.00End of Workshop