Graph-Theoretic Concepts in Computer Science

On the Expected Runtime and the Success Probability of Evolutionary Algorithms (Invited Presentation).- n Points and One Line: Analysis of Randomized Games (Abstract of Invited Lecture).- Approximating Call-Scheduling Makespan in All-Optical Networks.- New Spectral Lower Bounds on the Bisection Width of Graphs.- Traversing Directed Eulerian Mazes (Extended Abstract).- On the Space and Access Complexity of Computation DAGs.- Approximating the Treewidth of AT-Free Graphs.- Split-Perfect Graphs: Characterizations and Algorithmic Use.- Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs.- Networks with Small Stretch Number (Extended Abstract).- Efficient Dispersion Algorithms for Geometric Intersection Graphs.- Optimizing Cost Flows by Modifying Arc Costs and Capacities.- Update Networks and Their Routing Strategies.- Computing Input Multiplicity in Anonymous Synchronous Networks with Dynamic Faults.- Diameter of the Knödel Graph.- On the Domination Search Number.- Efficient Communication in Unknown Networks.- Graph Coloring on a Coarse Grained Multiprocessor (Extended Abstract).- The Tree-Width of Clique-Width Bounded Graphs without K n,n .- Tree Spanners for Subgraphs and Related Tree Covering Problems.- Minimal Size of Piggybacked Information for Tracking Causality: A Graph-Based Characterization.- The Expressive Power and Complexity of Dynamic Process Graphs.- Bandwidth of Split and Circular Permutation Graphs.- Recognizing Graphs without Asteroidal Triples (Extended Abstract).- Budget Constrained Minimum Cost Connected Medians.- Coloring Mixed Hypertrees.- A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs.- Optimal Fault-Tolerant Routings for k-Connected Graphs with Smaller Routing Tables.

Ulrik Brandes ist Professor für Algorithmik am Fachbereich Informatik der Universität Konstanz.