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

Front Cover
Springer Science & Business Media, Oct 18, 2000 - Computers - 313 pages
The 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000) was held at Waldhaus Jakob, in Konstanz, Germany, on 15{ 17 June 2000. It was organized by the Algorithms and Data Structures Group of the Department of Computer and Information Science, University of K- stanz, and sponsored by Deutsche Forschungsgemeinschaft (DFG) and Univ- sit ̈atsgesellschaft Konstanz. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas in computer science, or by extracting new problems from applications. The goal is to present recent research results and to identify and explore directions for future research. The workshop looks back on a remarkable tradition of more than a quarter of a century. Previous Workshops have been organized in various places in Europe, and submissions come from all over the world. This year, 57 attendees from 13 di erent countries gathered in the relaxing atmosphere of Lake Constance, also known as the Bodensee. Out of 51 submis- ons, the program committee carefully selected 26 papers for presentation at the workshop. This selection re?ects current research directions, among them graph and network algorithms and their complexity, algorithms for special graph cl- ses, communication networks, and distributed algorithms. The present volume contains these papers together with the survey presented in an invited lecture by Ingo Wegener (University of Dortmund) and an extended abstract of the invited lecture given by Emo Welzl (ETH Zuric ̈ h).
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

On the Expected Runtime and the Success Probability of Evolutionary Algorithms
1
Analysis of Randomized Games
11
Approximating CallScheduling Makespan in AllOptical Networks
13
New Spectral Lower Bounds on the Bisection Width of Graphs
23
Traversing Directed Eulerian Mazes
35
On the Space and Access Complexity of Computation DAGs
47
Approximating the Treewidth of ATFree Graphs
59
Characterizations and Algorithmic Use
71
On the Domination Search Number
161
Efficient Communication in Unknown Networks
172
Graph Coloring on a Coarse Grained Multiprocessor
184
The TreeWidth of CliqueWidth Bounded Graphs without Knn
196
Tree Spanners for Subgraphs and Related Tree Covering Problems
206
A GraphBased Characterization
218
The Expressive Power and Complexity of Dynamic Process Graphs
230
Bandwidth of Split and Circular Permutation Graphs
243

Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs
83
Networks with Small Stretch Number
95
E cient Dispersion Algorithms for Geometric Intersection Graphs
107
Optimizing Cost Flows by Modifying Arc Costs and Capacities
116
Update Networks and Their Routing Strategies
127
Computing Input Multiplicity in Anonymous Synchronous Networks with Dynamic Faults
137
Diameter of the Knodel Graph
149
Recognizing Graphs without Asteroidal Triples
255
Budget Constrained Minimum Cost Connected Medians
267
Coloring Mixed Hypertrees
279
A LinearTime Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs
290
Optimal FaultTolerant Routings for kConnected Graphs with Smaller Routing Tables
302
Author Index
314
Copyright

Other editions - View all

Common terms and phrases