Graph-Theoretic Concepts in Computer Science : 26th International Workshop, WG 2000 Konstanz, Germany, June 15-17, 2000 Proceedings

by Brandes, Ulrik

• ISBN13: 9783540411833
• ISBN10: 3540411836
• Format: Paperback
• Copyright: 2000-11-01
• Publisher: Springer Verlag

Summary

This book constitutes the thoroughly refereed post-workshop proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2000, held in Konstanz, Germany, in June 2000. The 26 revised full papers presented together with two invited contributions were carefully reviewed and selected from 51 submissions. The papers provide a wealth of new results for various classes of graphs, graph computations, graph algorithms and graph-theoretical applications in various fields.

Table of Contents

Invited Lecture: On the Expected Runtime and the Success Probability of Evolutionary Algorithms	1	(11)
Ingo Wegener
Invited Lecture: n Points and One Line: Analysis of Randomized Games	11	(2)
Emo Welzl
Approximating Call-Scheduling Makespan in All-Optical Networks	13	(10)
Luca Becchetti
Miriam Di Ianni
Alberto Marchetti-Spaccamela
New Spectral Lower Bounds on the Bisection Width of Graphs	23	(12)
Sergei L. Bezrukov
Robert Elsasser
Burkhard Monien
Robert Preis
Jean-Pierre Tillich
Traversing Directed Eulerian Mazes	35	(12)
Sandeep Bhatt
Shimon Even
David Greenberg
Rafi Tayar
On the Space and Access Complexity of Computation DAGs	47	(12)
Gianfranco Bilardi
Andrea Pietracaprina
Paolo D'Alberto
Approximating the Treewidth of AT-Free Graphs	59	(12)
Vincent Bouchitte
Ioan Todinca
Split-Perfect Graphs: Characterizations and Algorithmic Use	71	(12)
Andreas Brandstadt
Van Bang Le
Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs	83	(12)
Edson Caceres
Albert Chan
Frank Dehne
Giuseppe Prencipe
Networks with Small Stretch Number	95	(12)
Serafino Cicerone
Gabriele Di Stefano
Efficient Dispersion Algorithms for Geometric Intersection Graphs	107	(9)
Peter Damaschke
Optimizing Cost Flows by Modifying Arc Costs and Capacities	116	(11)
Ingo Demgensky
Hartmut Noltemeier
Hans-Christoph Wirth
Update Networks and Their Routing Strategies	127	(10)
Michael J. Dinneen
Bakhadyr Khoussainov
Computing Input Multiplicity in Anonymous Synchronous Networks with Dynamic Faults	137	(12)
Stefan Dobrev
Diameter of the Knodel Graph	149	(12)
Guillaume Fertin
Andre Raspaud
Heiko Schroder
Ondrej Sykora
Imrich Vrto
On the Domination Search Number	161	(11)
Fedor Fomin
Dieter Kratsch
Haiko Muller
Efficient Communication in Unknown Networks	172	(12)
Luisa Gargano
Andrzej Pelc
Stephane Perennes
Ugo Vaccaro
Graph Coloring on a Coarse Grained Multiprocessor	184	(12)
Assefaw Hadish Gebremedhin
Isabelle Guerin Lassous
Jens Gustedt
Jan Arne Telle
The Tree-Width of Clique-Width Bounded Graphs Without Kn,n	196	(10)
Frank Gurski
Egon Wanke
Tree Spanners for Subgraphs and Related Tree Covering Problems	206	(12)
Dagmar Handke
Guy Kortsarz
Minimal Size of Piggybacked Information for Tracking Causality: A Graph-Based Characterization	218	(12)
Jean Michel Helary
Giovanna Melideo
The Expressive Power and Complexity of Dynamic Process Graphs	230	(13)
Andreas Jakoby
Maciej Liskiewicz
Rudiger Reischuk
Bandwidth of Split and Circular Permutation Graphs	243	(12)
Ton Kloks
Dieter Kratsch
Yvan Le Borgne
Haiko Muller
Recognizing Graphs without Asteroidal Triples	255	(12)
Ekkehard Kohler
Budget Constrained Minimum Cost Connected Medians	267	(12)
Goran Konjevod
Sven O. Krumke
Madhav Marathe
Coloring Mixed Hypertrees	279	(11)
Daniel Kral
Jan Kratochvil
Andrzej Proskurowski
Heinz-Jurgen Voss
A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs	290	(12)
Sayaka Nagai
Shin-ichi Nakano
Optimal Fault-Tolerant Routings for k-Connected Graphs with Smaller Routing Tables	302	(13)
Koichi Wada
Wei Chen
Author Index	315