From dmanet@math.utwente.nl Tue May 4 01:45:57 1999 Date: Mon, 3 May 1999 15:55:29 +0200 From: Discrete Mathematics and Algorithms Network Reply-To: wg99@inf.ethz.ch To: DMA-LIST@NIC.SURFNET.NL Subject: WG'99 - Call for participation =============================================================================== CALL FOR PARTICIPATION =============================================================================== 25th International Workshop on Graph-Theoretic Concepts in Computer Science WG'99 - Ascona, http://www.inf.ethz.ch/wg99/ June 17 - 19, 1999 =============================================================================== Please find below the program of WG'99 and the registration form. Please register early. You will be sent an acknowledgement email. More information can be found on the WG'99 web-page at: http://www.inf.ethz.ch/wg99/ Hoping to see you soon in beautiful Ascona, Switzerland ... the WG'99 Organizing Committee =============================================================================== PROGRAM =============================================================================== =============================================================================== WEDNESDAY June 16, 1999 =============================================================================== The registration office is open throughout the afternoon. 19:00 Reception =============================================================================== THURSDAY June 17, 1999 =============================================================================== 08:30 Invited Lecture: Online Algorithms S. Albers ------------------------------------------------------------------------------- 09:30 Coffee Break ------------------------------------------------------------------------------- 09:45 Proximity-preserving Labeling Schemes and Their Applications D. Peleg 10:10 Euler is Standing in Line S. O. Krumke, D. Hauptmeier, J. Rambau, H.-C. Wirth 10:35 Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2 S. Ott ------------------------------------------------------------------------------- 11:00 Coffee Break ------------------------------------------------------------------------------- 11:25 Complexity Classification of Some Edge Modification Problems A. Natanzon, R. Shamir, R. Sharan 11:50 On Minimum Diameter Spanning Trees under Reload Costs H.-C. Wirth, J. Steffan 12:15 Maximum Induced Matching on Regular Graphs and Trees M. Zito ------------------------------------------------------------------------------- 12:40 Lunch Break ------------------------------------------------------------------------------- 14:40 Mod-2 Independence and Domination in Graphs M.Halldorson, J. Kratochvil, J. A. Telle 15:05 NLC2-Decomposition in Polynomial Time O. Johansson 15:30 On the Nature of Structure and its Identification B. Stein, O. Niggemann ------------------------------------------------------------------------------- 15:55 Coffee Break ------------------------------------------------------------------------------- 16:20 On the Clique-Width of Perfect Graph Classes M. C. Golumbic, U. Rotics 16:45 An Improved Algorithm for Finding Tree Decompositions of Small Width L. Perkovic, B. Reed 17:10 Efficient Analysis of Graphs with Small Minimal Separators K. Skodinis 17:35 Generating all the Minimal Separators of a Graph A. Berry, J.-P. Bordat, O. Cogis ------------------------------------------------------------------------------- 18:00 Break ------------------------------------------------------------------------------- 18:15 Visit of Casa Anatta Museum ------------------------------------------------------------------------------- 19:00 Dinner Break ------------------------------------------------------------------------------- 20:30 Stefano Franscini Lecture: Informatica, Scuola, Comunita': Uno Sguardo dall' Occhio del Ciclone N. Santoro 21:30 PC meeting =============================================================================== FRIDAY June 18, 1999 =============================================================================== 08:30 Optimal Broadcasting in Hypercubes with Dynamic Faults S. Dobrev, I. Vrto 08:55 Routing Permutations in the Hypercube O. Baudon, G. Fertin, I. Havel 09:20 An Optimal Fault-Tolerant Routing for Triconnected Planar Graphs K. Wada, Y. Nagata, W. Chen ------------------------------------------------------------------------------- 09:45 Coffee Break ------------------------------------------------------------------------------- 10:10 Optimal Irreversible Dynamos in Chordal Rings P. Flocchini, F. Geurts, N. Santoro 10:35 Recognizing Bipartite Incident-Graphs of Circulant Digraphs J. Cohen, P. Fraigniaud, C. Gavoille 11:00 Optimal Cuts for Powers of the Petersen Graph S.L. Bezrukov, S.K. Das, R. Elsaesser 11:25 Dihamiltonian Decomposition of Regular Graphs with Degree Three J.-H. Park and H.-C. Kim ------------------------------------------------------------------------------- 11:50 Coffee Break ------------------------------------------------------------------------------- 12:15 Box-Rectangular Drawings of Plane Graphs S. Rahman, S. Nakano, T. Nishizeki 12:40 A Multi-Scale Algorithm for Drawing Graphs Nicely D. Harel, R. Hadany 13:05 All Separating Triangles in a Plane Graph can be Optimally "broken" in Polynomial Time A. Accornero, M. Ancona ------------------------------------------------------------------------------- 13:30 Lunch Break ------------------------------------------------------------------------------- 14:30 Excursion 19:00 Invited Lecture: SILVER GRAPHS: Achievements and New Challenges H. Noltemeier 19:30 Conference Dinner =============================================================================== SATURDAY June 19, 1999 =============================================================================== 08:30 Invited Lecture: Discrete Optimization Methods for Packing Problems in Two and Three Dimensions - With Applications in the Textile and Car Manufacturing Industries T. Lengauer ------------------------------------------------------------------------------- 09:30 Coffee Break ------------------------------------------------------------------------------- 09:45 Linear Orderings of Random Geometric Graphs J. Diaz, M. D. Penrose, J. Petit, M. Serna 10:10 Finding Smallest Supertrees under Minor Containment N. Nishimura, P. Ragde, D. M. Thilikos 10:35 Vertex Cover: Further Observations and Further Improvements J. Chen, I. Kanj, W. Jia ------------------------------------------------------------------------------- 11:00 Coffee Break ------------------------------------------------------------------------------- 11:25 On the Hardness of Recognizing Bundles in Time Table Graphs A. Liebers, D. Wagner, K. Weihe 11:50 Optimal solutions for Frequency Assignment Problems via Tree-Decomposition A.M.C.A. Koster, C.P.M. van Hoesel and A. W.J. Kolen 12:15 Fixed-Parameter Complexity of lambda-Labelings J. Fiala, T. Kloks, J. Kratochvil ------------------------------------------------------------------------------- 12:40 Lunch Break ------------------------------------------------------------------------------- 14:15 Efficient Algorithms for Hamiltonian Problems on (Claw, Net)-free Graphs A. Brandstaedt, F. F. Dragan, E. Koehler 14:40 On Claw-free Asteroidal Triple-Free Graphs H. Hempel, D. Kratsch 15:05 Vertex Partitioning of Crown-free Interval Graphs G. Confessore, P. Dell'Olmo, S. Giordani 15:30 Triangulated Neighbourhoods in C4-free Berge Graphs I. Parfenoff, F. Roussel, I. Rusu ------------------------------------------------------------------------------- 15:55 End of Workshop ------------------------------------------------------------------------------- -- cut here --- cut here --- cut here --- cut here --- cut here --- cut here -- ============================================================================ REGISTRATION FORM ============================================================================ The registration fee is CHF 400.-- (Swiss Francs) if you register before May 21, 1999. The fee covers lodging, meals, a volume of the proceedings, the excursion, the reception, and the conference dinner. After May 21, 1999, a late registration fee of CHF 500.-- will be collected. Since attendance is limited, registration will be accepted first-come first-serve. To register, please fill out one form for each participant. Fax it to ++41 1 632 1399, or email to: wg99@inf.ethz.ch, subject: REGISTRATION Name: ________________________ First Name: __________________ Sex: _______ Affiliation: _______________________________________________________________ Address: ___________________________________________________________________ ____________________________________________________________________________ ____________________________________________________________________________ Phone: _______________________________ Fax: _______________________________ E-mail: ____________________________________________________________________ Dietary restrictions (we'll try to do our best): __________________________ Only very few single rooms are available. Therefore, you should expect to share your room. Desired partner for room sharing (if any): _________________________________ Payment will be due upon registration at the conference venue. You will have the option of charging your credit card or paying cash. However, to confirm your registration you *must* provide the following credit card information (for either payment method), now: American Express: [ ] Visa: [ ] Master: [ ] Credit Card No.: __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ Expiration Date: __ __ __ __ Name of Card Holder: (use exact spelling) ____________________________________________________________________________ Please sign (if you fax this form): ____________________________________________________________________________ ****************************************************** Contributions to be spread via DMANET are submitted to DMANET@math.utwente.nl Replies to a message carried on DMANET should NOT be addressed to DMANET but to the original sender. The original sender, however, is invited to prepare an update of the replies received and to communicate it via DMANET. DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET) http://www.math.utwente.nl/stor/OR/dmanet.html