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

بیست و ششمین کارگاه بین المللی مفاهیم نظری گراف در علوم کامپیوتر (WG 2000) در Waldhaus Jakob، در کنستانز، آلمان، در 15{17 ژوئن 2000 برگزار شد. این کارگاه توسط گروه الگوریتم ها و ساختارهای داده این دپارتمان سازماندهی شد. علوم کامپیوتر و اطلاعات، دانشگاه K-stanz، و توسط Deutsche Forschungsgemeinschaft (DFG) و Univ-sit¨atsgesellschaft Konstanz حمایت می شود. این کارگاه با نشان دادن اینکه چگونه مفاهیم نظری گراف را می توان در زمینه های مختلف علوم کامپیوتر به کار برد، یا با استخراج مسائل جدید از برنامه ها، تئوری و عمل را متحد کرد. هدف ارائه نتایج تحقیقات اخیر و شناسایی و کشف مسیرهای تحقیقات آتی است. این کارگاه به یک سنت قابل توجه بیش از ربع قرن نگاه می کند. کارگاه های قبلی در نقاط مختلف اروپا سازماندهی شده است و آثار ارسالی از سراسر جهان ارائه شده است. امسال، 57 شرکت کننده از 13 کشور مختلف در فضای آرام دریاچه کنستانس، که به آن Bodensee نیز معروف است، گرد هم آمدند. از بین 51 مقاله ارسالی، کمیته برنامه با دقت 26 مقاله را برای ارائه در کارگاه انتخاب کرد. این انتخاب، جهت‌های تحقیقاتی فعلی، از جمله الگوریتم‌های گراف و شبکه و پیچیدگی آن‌ها، الگوریتم‌های گراف‌های ویژه، شبکه‌های ارتباطی، و الگوریتم‌های توزیع‌شده را بازتاب می‌دهد. جلد حاضر شامل این مقالات همراه با نظرسنجی ارائه شده در یک سخنرانی دعوت شده توسط اینگو وگنر (دانشگاه دورتموند) و چکیده ای مبسوط از سخنرانی دعوت شده توسط ایمو ولزل (ETH Zuric ¨ h) است.

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).