Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Germany, June 15-17, 2000 ProceedingsThe 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). |
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 Kn ̈odel 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 |
| 314 | |
Other editions - View all
Graph-Theoretic Concepts in Computer Science Ulrik Brandes,Dorothea Wagner No preview available - 2014 |
Graph-Theoretic Concepts in Computer Science: 26th International Workshop ... Ulrik Brandes No preview available - 2000 |
Common terms and phrases
approximation algorithm AT-free graphs bandwidth BCCMED biconnected bipartite graph block broadcasting called CDAG chordal graph clique clique-width colors complete Computer Science connected component consider contains corresponding defined denote directed graph disjoint distance evolutionary algorithms flow cost full component associated function given graph G Hence hypergraph hypertree independent set induced subgraph integer interval graphs k-connected k-connected graph knotting graph label least Lemma Let G linear LNCS lower bound maximal maximum minimal separator minimum n-node neighbors NLC-width nodes NP-complete NP-hard observable events optimal pair parallel partition path permutation graphs phase planar planar graph polynomial PQ-tree problem processor Proof protocol Ramanujan graphs representation round route degree schedule searchers spanning trees split graph split-perfect graphs Steiner tree k-spanner Steiner vertices step stretch number subset subtree Theorem timeslots total number tree-width triangles undirected update network v₁ vertex set