From owner-theorynt@LISTSERV.NODAK.EDU Tue Jun 10 13:24:31 1997 Received: from Sunburn.Stanford.EDU (Sunburn.Stanford.EDU [171.64.67.178]) by robotics.Stanford.EDU (8.8.5/8.8.5) with ESMTP id NAA09480 for ; Tue, 10 Jun 1997 13:24:31 -0700 (PDT) Received: from listserv.nodak.edu (listserv.NoDak.edu [134.129.111.8]) by Sunburn.Stanford.EDU (8.8.4/8.8.4) with ESMTP id NAA10413; Tue, 10 Jun 1997 13:14:29 -0700 (PDT) Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.08BF4D20@listserv.nodak.edu>; Tue, 10 Jun 1997 15:07:38 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 703762 for THEORYNT@LISTSERV.NODAK.EDU; Tue, 10 Jun 1997 15:07:33 -0500 Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.057A8260@listserv.nodak.edu>; Tue, 10 Jun 1997 15:07:32 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 703750 for THEORY-A@LISTSERV.NODAK.EDU; Tue, 10 Jun 1997 15:07:32 -0500 Received: from usc.edu by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.04828DD0@listserv.nodak.edu>; Tue, 10 Jun 1997 15:07:31 -0500 Received: from pollux2.usc.edu (pollux2.usc.edu [128.125.253.192]) by usc.edu (8.8.4/8.7.2/usc) with ESMTP id NAA02649 for ; Tue, 10 Jun 1997 13:07:28 -0700 (PDT) Received: (from ierardi@localhost) by pollux2.usc.edu (8.8.4/8.8.4/usc) id NAA04025 for theory-a@listserv.nodak.edu; Tue, 10 Jun 1997 13:06:58 -0700 (PDT) X-Mailer: ELM [version 2.4 PL25] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Approved-By: Doug Ierardi Approved-By: Theory-A - TheoryNet World-Wide Events Message-ID: <199706051433.KAA11624@roger.scs.carleton.ca> Date: Tue, 10 Jun 1997 13:06:57 PDT Reply-To: Theory-A - TheoryNet World-Wide Events , sirocco Sender: TheoryNet List From: sirocco Subject: SIROCCO - Accepted Papers Comments: To: THEORY-A@LISTSERV.NODAK.EDU To: THEORYNT@LISTSERV.NODAK.EDU X-Mozilla-Status: 0001 Content-Length: 1931 List of accepted papers ----------------------- About the local detection of termination of local computations in graphs Y. Metivier, A. Muscholl and P. Wacrenier An Empirical Study of ``Lazy'' Protocols for Routing Information in Dynamic Networks F. Annexstein and C. Giannella An $\Omega (n^2)$-Lower Bound for Space-Efficiency of Routing Schemes of Stretch Factor Three C. Gavoille and M. Gengler An optimal algorithm for broadcasting multiple messages in trees K. Diks, A. Lingas and A. Pelc An Optimal Lower Bound for Interval Routing in General Networks S.S.H. Tse and F.C.M. Lau Approximating Minimum Communication Spanning Trees D. Peleg Bandwidth Allocation Algorithms on Tree--Shaped All--Optical=20 Networks with Wavelength Converters V. Auletta, I. Caragiannis, C. Kaklamanis and G. Persiano Better Expanders and Superconcentrators by Kolmogorov Complexity U. Sch=F6ning Bounds for the On-line Multicast Problem in Directed Graphs M. Faloutsos, R. Pankaj and K.C. Sevcik Compact Routing on Chordal Rings L. Narayanan and J. Opatrny Computing Vector Functions on Anonymous Networks P. Boldi and S. Vigna Duality in Chain ATM Virtual Path Layouts M. Feighelstein and S. Zaks Embedding Tori in Partitioned Optical Passive Star Networks P.Berthome, J.Cohen, A.Ferreira Heuristics Algorithms for Personalized Communication Problems in Point-to-Point Networks P. Fraigniaud and S. Vial Linear broadcasting and N log log N election in unoriented hypercubes S. Dobrev and P. Ruzicka On Computing Nearly Optimal Multi-Tree Paths and $s,t$-Numberings F.S. Annexstein, K.A. Berman and R. Swaminathan Optimal gossip in noncombining 2D-meshes M. Soch and P. Tvrdik Size Bounds for Dynamic Monopolies D. Peleg Static Frequency Assignment in Cellular Networks L. Narayanan and S. Shende The Complexity of Characterization of Networks Supporting=20 Shortest-Path Interval Routing T. Eilam, S. Moran and S. Zaks From owner-dma-list@NIC.SURFNET.NL Wed Jun 25 08:36:50 1997 Received: from CS.Stanford.EDU (CS.Stanford.EDU [171.64.64.64]) by robotics.Stanford.EDU (8.8.5/8.8.5) with ESMTP id IAA04344; Wed, 25 Jun 1997 08:36:50 -0700 (PDT) Received: from hearnnt.nic.surfnet.nl (hearnnt.nic.surfnet.nl [192.87.5.133]) by CS.Stanford.EDU (8.8.4/8.8.4) with ESMTP id IAA17660; Wed, 25 Jun 1997 08:36:27 -0700 (PDT) Received: from hearnnt (192.87.5.133) by hearnnt.nic.surfnet.nl (LSMTP for Windows NT v1.1a) with SMTP id <0.CB1E1750@hearnnt.nic.surfnet.nl>; Wed, 25 Jun 1997 17:32:45 +0200 Received: from NIC.SURFNET.NL by NIC.SURFNET.NL (LISTSERV release 1.8c) with NJE id 4555 for DMA-LIST@NIC.SURFNET.NL; Wed, 25 Jun 1997 17:36:33 +0200 Received: from HEARN (NJE origin SMTP@HEARN) by HEARN.NIC.SURFNET.NL (LMail V1.2c/1.8c) with BSMTP id 0594; Wed, 25 Jun 1997 17:36:32 +0200 Received: from utmfu6.math.utwente.nl by HEARN.nic.SURFnet.nl (IBM VM SMTP V2R2) with TCP; Wed, 25 Jun 97 17:36:30 +0200 Received: from utmfu0.math.utwente.nl (utmau6.math.utwente.nl) by utmfu6.math.utwente.nl with ESMTP (1.40.112.8/16.2) id AA011382969; Wed, 25 Jun 1997 17:36:10 +0200 Received: by utmfu0.math.utwente.nl ($Revision: 1.36.108.11 $/16.2) id AA173752967; Wed, 25 Jun 1997 17:36:07 +0200 Mailer: Elm [revision: 66.36.1.1] Mime-Version: 1.0 Content-Transfer-Encoding: quoted-printable Approved-By: DMANET Message-ID: <199706251536.AA173752967@utmfu0.math.utwente.nl> Date: Wed, 25 Jun 1997 17:36:05 METDST Reply-To: sirocco@inf.ethz.ch Sender: DMANET From: DMANET Subject: SIROCCO 97 - Call for Participation To: DMA-LIST@NIC.SURFNET.NL Status: O X-Mozilla-Status: 0001 Content-Length: 11542 CALL FOR PARTICIPATION SIROCCO 97 =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D International Colloquium on Structural Information & Communication Complexity http://www.scs.carleton.ca/~sirocco/ Centro Stefano Franscini Monte Verita, Ascona Switzerland July 24 - 26, 1997 General Information, Programme & Registration Form -------------------------------------------------------------------------= ----- General Information ------------------- The 4th Colloquium on Structural Information and Communication Complexity= will = focus on the relationship between computing and communication, i.e., the = study = of those factors which are significant for the computability and the = communication complexity of problems, and on the interplay between struct= ure, = knowledge and complexity in systems of communicating agents. The Colloqui= um is = designed to bring together researchers interested in the fundamental = principles underlying all computing through communication. = The colloquium will take place at the Centro Stefano Franscini on the Mon= te = Verita above Ascona, in the Italian speaking part of Switzerland. On the = shores of Lake Maggiore, Ascona (Canton Ticino) enjoys a Mediterranean cl= imate = in an alpine setting. With over 2,300 hours of sunshine per year, Ascona = is = Switzerland's sunniest place; the average July temperature varies between= 20=B0C = and 30=B0C during the day. The average water temperature in July of Lake = Maggiore is 23=B0C. = Excellent train connections exist from Milano or Zurich to the area of th= e = meeting. It takes less than 2 hours (3 hours) to travel from Milano (from= = Zurich) to Ascona/Locarno by train. We will provide a bus-service from th= e = station to the Centro Stefano Franscini. The Canton Ticino has a tiny air= port = of its own: Lugano-Agno. From Lugano-Agno Crossair (the Swiss regional ai= rline) = flights link business people to some European cities. For further information about the colloquium, the Centro Stefano Franscin= i, = for further touristic information and pictures, and information on = transportation, please contact http://www.scs.carleton.ca/~sirocco/ or SIROCCO 97 = Roger Wattenhofer = Institut fuer Theoretische Informatik = ETH Zurich 8092 Zurich, Switzerland sirocco@inf.ethz.ch -------------------------------------------------------------------------= ----- Colloquium Programme -------------------- WEDNESDAY, JULY 23 20:00 Welcome Reception & Dinner THURSDAY, JULY 24 Session 1: 09:00 - 9:50 09:00 Invited Talk: Theoretical Research on Networks: Models and = Methodology A. Rosenberg, Amherst Break Session 2: 10:00 - 10:50 10:00 Approximating Minimum Communication Spanning Trees = D. Peleg, Weizmann = 10:25 On Computing Nearly Optimal Multi-Tree Paths and s,t-Numberings= = F.S. Annexstein, K.A. Berman and R. Swaminathan, Cincinnati, Cincinnati, Lucent = Coffee Break = Session 3: 11:10 - 12:30 = 11:10 Bandwidth Allocation Algorithms on Tree-Shaped All-Optical = Networks with Wavelength Converters = V. Auletta, I. Caragiannis, C. Kaklamanis and G. Persiano, Salerno, Patras, Patras, Salerno = 11:35 Embedding Tori in Partitioned Optical Passive Star Networks = P. Berthome, J. Cohen, A. Ferreira, Paris Sud, ENS Lyon, ENS Ly= on = 12:00 Open Problems & Research Directions = Lunch Break = Session 4: 15:00 - 16:15 = 15:00 Linear Broadcasting and N loglog N Election in Unoriented Hyper= cubes = S. Dobrev and P. Ruzicka, Comenius Bratislava = 15:25 An Optimal Algorithm for Broadcasting Multiple Messages in Tree= s = K. Diks, A. Lingas and A. Pelc, Warszawa, Lund, Hull = 15:50 Bounds for the On-line Multicast Problem in Directed Graphs = M. Faloutsos, R. Pankaj and K.C. Sevcik, Toronto = Coffee Break = Session 5: 16:30 - 18:30 = 16:30 The Complexity of Characterization of Networks Supporting Shortest-Path Interval Routing = T. Eilam, S. Moran and S. Zaks, Technion = 16:55 An Optimal Lower Bound for Interval Routing in General Networks= = S.S.H. Tse and F.C.M. Lau, Hong Kong = 17:20 Compact Routing on Chordal Rings = L. Narayanan and J. Opatrny, Concordia Montreal 18:00 Open Public Talk: Informatica, Societa ed Educazione J. Nievergelt, ETH Zurich Dinner = FRIDAY, JULY 25 = = Session 1: 09:00 - 9:50 = 09:00 Invited Talk: How to use Gossiping Theory and Two-Party = Communication Complexity for Analyzing the Cost of Computing = Functions in Synchronous and Asynchronous Networks = M. Dietzfelbinger, Dortmund = Break = Session 2: 10:00 - 10:50 = 10:00 Better Expanders and Superconcentrators by Kolmogorov Complexit= y = U. Schoening, Ulm = 10:25 Size Bounds for Dynamic Monopolies = D. Peleg, Weizmann = = Coffee Break = Session 3: 11:10 - 11:50 = 11:10 An Omega(n^2)-Lower Bound for Space-Efficiency of Routing Schemes of Stretch Factor Three = C. Gavoille and M. Gengler, Bordeaux, ENS Lyon = 11:35 An Empirical Study of ``Lazy'' Protocols for Routing Information in Dynamic Networks = F. Annexstein and C. Giannella, Cincinnati = Lunch Break = Session 4: 14:00 - 14:50 = 14:00 About the Local Detection of Termination of Local Computations in Graphs = Y. Metivier, A. Muscholl and P. Wacrenier, Bordeaux = 14:25 Computing Vector Functions on Anonymous Networks = P. Boldi and S. Vigna, Milano = Excursion & Conference Dinner = SATURDAY, JULY 26 = Session 1: 09:00 - 9:50 = 09:00 Invited Talk: Efficient Flow Control in Networks = P. Spirakis, Patras = Break = Session 2: 10:00 - 10:50 = 10:00 Static Frequency Assignment in Cellular Networks = L. Narayanan and S. Shende, Concordia Montreal, Lincoln = 10:25 Duality in Chain ATM Virtual Path Layouts = M. Feighelstein and S. Zaks, Technion = Coffee Break = Session 3: 11:10 - 12:30 = 11:10 Heuristics Algorithms for Personalized Communication Problems i= n Point-to-Point Networks = P. Fraigniaud and S. Vial, ENS Lyon = 11:35 Optimal Gossip in Noncombining 2D-Meshes = M. Soch and P. Tvrdik, Praha = 12:00 Open Problems & Rump Session = Lunch & End of the Colloquium = -------------------------------------------------------------------------= ----- Call for Rump Session Contributions ----------------------------------- The rump sessions are intended for presentation of unpolished recent resu= lts, = description of current research efforts, informal exposition of publishe= d = or submitted results. If interested in contributing, notify the PC chairs= at = the Colloquium. Call for Open Problems = ---------------------- You are invited to submit open problems for presentation at the Colloquiu= m. = Possibly, your submission should contain a statement of the problem, = background information, known partial results, and any other relevant = information. All contributed open problems will appear in the final = proceedings with the name of the contributors. Submit directly at the = Colloquium. Colloquium Registration (Deadline: July 8, 1997) = ----------------------- = The registration fee is USD 450 or CHF 630 (students are encouraged to ap= ply = for scholarships). The fee includes all expenses (board and lodging, all = colloquium events, and the volume of the proceedings). Pre-proceedings = containing a copy of all accepted papers will be available at the Colloqu= ium. = The final proceedings will be published and mailed to all participants af= ter = the colloquium. The Registration Form and the student certification (if applicable) must= be returned before July 8. The recommended mode of payment is by credit card= , = but you can also pay by ec-direct, or cash (Swiss Francs). Program Committee ----------------- = Hans Bodlaender [Utrecht] Christos Kaklamanis [Patras] Danny Krizanc [Carleton] = Bernard Mans [Macquarie] Ernst Mayr [Munich] Umberto Nanni [Rome] Jose Rolim [Geneva] Arny Rosenberg [Amherst] Nicola Santoro [Carleton] Dominique Sotteau [Paris-Sud] Imrich Vrto [Bratislava] Peter Widmayer [ETH Zurich] Organizing Committee = -------------------- Colloquium Chair: = Roger Wattenhofer [ETH Zurich] Program Chairs: = Danny Krizanc [Carleton] = Peter Widmayer [ETH Zurich] Publicity: = Paola Flocchini [Montreal] Local Organisation: = Katia Bastianelli [CSF Ascona] = -------------------------------------------------------------------------= ----- SIROCCO 97 Centro Stefano Franscini Monte Verita , Ascona = July 24 - 26 1997 = Registration Form = ----------------- First Name: = Last name: Affiliation: = Address: = Postal Code & City: = Country: = Phone: = Fax: = Email: = Credit Card: [] Eurocard/Mastercard [] Visa [] American Express [] Din= er's Club Number: = Expiration Date: = [] I would like to have vegetarian meals = I would like to board the bus at the station at [] 15:10 [] 18:10 [] 20= :10 = I would like to share a room with: Please indicate any special needs: = Signature: = -------------------------------------------------------------------------= ----- SIROCCO 97 = Centro Stefano Franscini Monte Verita , Ascona = July 24 - 26 1997 APPLICATION FOR FULL-TIME STUDENT SCHOLARSHIP --------------------------------------------- We have limited funds available that we will distribute fairly among the = applying students in financial need. Unless the number of applications is= very = high, a scholarship will cover the entire registration fee. Please have this filled and signed by your advisor. = I certify that: is a full time student at: Name (Please print): = Position: = Signature: = -------------------------------------------------------------------------= ----- The Registration Form and the Application for full-time student scholarsh= ip (if applicable) must be returned by mail, email, or fax before JULY 8 to:= SIROCCO 97 = Roger Wattenhofer = Institut f=FCr Theoretische Informatik = ETH Zurich 8092 Zurich, Switzerland sirocco@inf.ethz.ch fax: +41 - 1 632 11 72 -- ****************************************************** 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)