From owner-theorynt@LISTSERV.NODAK.EDU Tue May 13 16:51:26 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 QAA28831 for ; Tue, 13 May 1997 16:51:26 -0700 (PDT) Received: from listserv.nodak.edu (listserv.NoDak.edu [134.129.111.8]) by CS.Stanford.EDU (8.8.4/8.8.4) with ESMTP id QAA11888; Tue, 13 May 1997 16:39:52 -0700 (PDT) Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.159DD190@listserv.nodak.edu>; Tue, 13 May 1997 18:40:09 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 182434 for THEORYNT@LISTSERV.NODAK.EDU; Tue, 13 May 1997 18:40:05 -0500 Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.13534550@listserv.nodak.edu>; Tue, 13 May 1997 18:40:05 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 182425 for THEORY-A@LISTSERV.NODAK.EDU; Tue, 13 May 1997 18:40:05 -0500 Received: from pollux.usc.edu by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.1288A250@listserv.nodak.edu>; Tue, 13 May 1997 18:40:04 -0500 Received: (from ierardi@localhost) by pollux.usc.edu (8.8.4/8.8.4/usc) id QAA10093 for theory-a@listserv.nodak.edu; Tue, 13 May 1997 16:40:02 -0700 (PDT) X-Mailer: ELM [version 2.4 PL24++ PGP2] Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Approved-By: Doug Ierardi Approved-By: Theory-A - TheoryNet World-Wide Events Message-ID: <199705051144.AA13383@roo.math.TU-Berlin.DE> Date: Tue, 13 May 1997 16:40:00 PDT Reply-To: Theory-A - TheoryNet World-Wide Events , Stephan Hartmann Sender: TheoryNet List From: Stephan Hartmann Subject: WG'97 -> accepted papers Comments: To: THEORY-A@LISTSERV.NODAK.EDU To: THEORYNT@LISTSERV.NODAK.EDU X-Mozilla-Status: 0001 Content-Length: 2758 This is the list of accepted papers to WG '97. Papers do not appear in alphabetic order in the list. For more info on the workshop see the URL: http://www.math.TU-Berlin.DE/~wg97 ---------------------------------------------------------------------------- Alimonti, Paola "Non-oblivious Local Search for MAX 2-CCSP with Application to MAX DICUT" Alt, Helmut; Fuchs Ulrich; Kriegel, Klaus "On the Number of Simple Cycles in Planar Graphs" Babel, Luitpold; Olariu, Stephan "On the Separable-Homogeneous Decomposition of Graphs" Babel, Luitpold; Woeginger, Gerhard J. "Pseudo-Hamiltonian Graphs" Bermond, Jean-Claude; Di Ianni, Miriam; Flammini, Michele "Acyclic Orientations for Deadlock Prevention in Interconnection Networks" Bertet, Karell; Gustedt, Jens; Morvan, Michel "Weak-Order Extensions of an Order" Bertoni, Alberto; Campadelli, Paola; Posenato, Roberto "An Upper Bound of the Maximum Cut Mean" Brandes, Ulrik; Handke, Dagmar "NP-Completeness Results for Minimum Planar Spanners" Brandt, Stephan "Computing the independence number of dense triangle-free graphs" Broersma, H. J.; Dahlhaus, E.; Kloks, T. "Algorithms for the treewidth and minimum fill-in of HHD-free graphs" Capelle, Christian "Block decomposition of inheritance hierarchies" Dahlhaus, Elias "Minimal Elimination Ordering Inside a Given Chordal Graph" d'Amore, Fabrizio; Iacobini, Fabio "On-line algorithms for networks of temporal constraints" de Fluiter, Babette; Bodlaender, Hans L. "Parallel Algorithms for Treewidth Two" Dinitz, Yefim; Feighelstein, Marcelo; Zaks, Shmuel "On Optimal Graphs Embedded into Paths and Rings, with Analysis using l_1-Spheres" Dragan, Feodor F. "On greedy matching ordering and greedy matched graphs" Erlebach, Thomas; Jansen, Klaus "Off-line and On-line Call-Scheduling in Stars and Trees" Hlineny, Petr; Kratochvil, Jan "Computational Complexity of the Krausz Dimension of Graphs" Kloks, Ton; Kratsch, Dieter; M"uller, Haiko "Asteroidal Sets in Graphs" Kratochvil, Jan; Proskurowksi, Andrzej; Telle, Jan Arne "Complexity of colored graph covers." Mosbah, M. "A Syntactic Approach to Random Walks on Graphs" Prisner, Erich "Bicliques in graphs II: Recognizing k-path graphs and underlying graphs of line digraphs" Sampels, Michael "Large Networks with Small Diameter" Skodinis, K. "The Bounded Tree-Width Problem of Context-Free Graph Languages" Thorup, Mikkel "Structured Programs have Small Tree-Width and Good Register Allocation" Uehara, Ryuhei "A Measure of Parallelization for the Lexicographically First Maximal Subgraph Problem" Vos, T. E. J.; Swierstra, S. D. "Make your enemies transparant." Wada, Koichi; Chen, Wei; Luo, Yupin; Kawaguchi, Kimio "Optimal Fault-tolerant ATM-Routings for Biconnected Graphs" From owner-theorynt@LISTSERV.NODAK.EDU Tue May 13 17:00:55 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 RAA28987 for ; Tue, 13 May 1997 17:00:55 -0700 (PDT) Received: from listserv.nodak.edu (listserv.NoDak.edu [134.129.111.8]) by CS.Stanford.EDU (8.8.4/8.8.4) with ESMTP id QAA12278; Tue, 13 May 1997 16:49:16 -0700 (PDT) Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.DA7F6E10@listserv.nodak.edu>; Tue, 13 May 1997 18:45:39 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 183805 for THEORYNT@LISTSERV.NODAK.EDU; Tue, 13 May 1997 18:45:36 -0500 Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.D7F4A480@listserv.nodak.edu>; Tue, 13 May 1997 18:45:35 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 183791 for THEORY-C@LISTSERV.NODAK.EDU; Tue, 13 May 1997 18:45:35 -0500 Received: from pollux.usc.edu by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.D59E3160@listserv.nodak.edu>; Tue, 13 May 1997 18:45:31 -0500 Received: (from ierardi@localhost) by pollux.usc.edu (8.8.4/8.8.4/usc) id QAA10479 for theory-c@listserv.nodak.edu; Tue, 13 May 1997 16:45:29 -0700 (PDT) X-Mailer: ELM [version 2.4 PL24++ PGP2] Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Approved-By: Doug Ierardi Approved-By: Theory-C - TheoryNet General Discussions Message-ID: <199705131418.AA08833@roo.math.TU-Berlin.DE> Date: Tue, 13 May 1997 16:45:28 PDT Reply-To: Stephan Hartmann Sender: TheoryNet List From: Stephan Hartmann Subject: WG'97 -> programme Comments: To: THEORY-C@LISTSERV.NODAK.EDU To: THEORYNT@LISTSERV.NODAK.EDU X-Mozilla-Status: 0001 Content-Length: 8880 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'97) Berlin, June 18 - 20, 1997 Attached is the complete programme and the registration form of WG'97, the 23rd International Workshop on GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE. The Workshop is held June 18-20, 1997 in Berlin, Germany. Everybody can register, but, due to limitations of the conference site, the number of non-speakers is limited to about 70. These places will be assigned on a first-come first-served basis. Registration deadline is June 1, 1997. After that, rooms will be no longer available. To register, simply send an e-mail with the specified subject to: wg97@math.TU-Berlin.DE Subject: REGISTRATION or use the form at the end of this mail. More information about the workshop (getting there, abstracts of lectures, social programme) is or will be available via WWW at URL http://www.math.TU-Berlin.DE/~wg97 We look forward to seeing you at WG'97. Sincerely, Rolf Moehring Chairman WG'97 ++++++++++++++++++++++++ WG'97 programme ++++++++++++++++++++++++++++++++ Tuesday, June 17, 1997 14:00 Opening of the conference office 18:30 Welcoming reception (including dinner) ============================================================= Wednesday, June 18, 1997 Session 1: 9:00 -- 11:00 Chair: Lefteris Kirousis 9:00 Thorup, Mikkel "Structured Programs have Small Tree-Width and Good Register Allocation" 9:30 Skodinis, Konstantin "The Bounded Tree-Width Problem of Context-Free Graph Languages" 10:00 Broersma, H. J.; Dahlhaus, Elias; Kloks, Ton "Algorithms for the Treewidth and Minimum Fill-in of HHD-free Graphs" 10:30 de Fluiter, Babette; Bodlaender, Hans L. "Parallel Algorithms for Treewidth Two" **** Coffee break 11:00 -11:30 ******************************** Session 2: 11:30 -- 13:00 Chair: Ernst W. Mayr 11:30 Babel, Luitpold; Woeginger, Gerhard J. "Pseudo-Hamiltonian Graphs" 12:00 Dragan, Feodor F. "On Greedy Matching Ordering and Greedy Matched Graphs" 12:30 Bertoni, Alberto; Campadelli, Paola; Posenato, Roberto "An Upper Bound of the Maximum Cut Mean" ***** Lunch 13:00 -15:00 ************************************* Session 3: 15:00 -- 16:00 (invited talk) Chair: Rolf H. Moehring 15:00 David Williamson "Gadgets, Approximation, and Linear Programming: Improving Hardness Results for Cut and Satisfiability Problems" **** Coffee break 16:00 -16:30 ****************************** Session 4: 16:30 -- 18:00 Chair: Alberto Marchetti-Spaccamela 16:30 Alimonti, Paola "Non-oblivious Local Search for MAX 2-CCSP with Application to MAX DICUT" 17:00 Erlebach, Thomas; Jansen, Klaus "Off-line and On-line Call-Scheduling in Stars and Trees" 17:30 Mosbah, M. "A Syntactic Approach to Random Walks on Graphs" ********* Dinner 19:00 *************************************** ============================================================= Thursday, June 19, 1997 Session 5: 9:00 -- 11:00 Chair: Hans L. Bodlaender 9:00 Kratochvil, Jan; Proskurowksi, Andrzej; Telle, Jan Arne "Complexity of Colored Graph Covers." 9:30 Capelle, Christian "Block Decomposition of Inheritance Hierarchies" 10:00 Kloks, Ton; Kratsch, Dieter; M"uller, Haiko "Asteroidal Sets in Graphs" 10:30 Babel, Luitpold; Olariu, Stephan "On the Separable-Homogeneous Decomposition of Graphs" **** Coffee break 11:00 -11:30 ******************************** Session 6: 11:30 -- 13:30 Chair: Peter Widmayer 11:30 Alt, Helmut; Fuchs Ulrich; Kriegel, Klaus "On the Number of Simple Cycles in Planar Graphs" 12:00 Brandes, Ulrik; Handke, Dagmar "NP-Completeness Results for Minimum Planar Spanners" 12:30 Dinitz, Yefim; Feighelstein, Marcelo; Zaks, Shmuel "On Optimal Graphs Embedded into Paths and Rings, with Analysis Using l_1-Spheres" 13:00 Sampels, Michael "Large Networks with Small Diameter" ***** Lunch 13:30 -15:00 ************************************* 15:00 Social Event & Conference Diner ============================================================= Friday, June 20, 1997 Session 7: 9:00 -- 11:00 Chair: Ondrej Sykora 9:00 Brandt, Stephan "Computing the Independence Number of Dense Triangle-free Graphs" 9:30 Hlineny, Petr; Kratochvil, Jan "Computational Complexity of the Krausz Dimension of Graphs" 10:00 Bertet, Karell; Gustedt, Jens; Morvan, Michel "Weak-Order Extensions of an Order" 10:30 Prisner, Erich "Bicliques in Graphs II: Recognizing k-path Graphs and Underlying Graphs of Line Digraphs" **** Coffee break 11:00 -11:30 ******************************** Session 8: 11:30 -- 13:00 Chair: Michel Habib 11:30 d'Amore, Fabrizio; Iacobini, Fabio "On-line Algorithms for Networks of Temporal Constraints" 12:00 Bermond, Jean-Claude; Di Ianni, Miriam; Flammini, Michele "Acyclic Orientations for Deadlock Prevention in Interconnection Networks" 12:30 Wada, Koichi; Chen, Wei; Luo, Yupin; Kawaguchi, Kimio "Optimal Fault-tolerant ATM-Routings for Biconnected Graphs" ***** Lunch 13:00 -15:00 ************************************* Session 9: 15:00 -- 16:30 Chair: Giorgio Ausiello 15:00 Dahlhaus, Elias "Minimal Elimination Ordering Inside a Given Chordal Graph" 15:30 Vos, Tanja E. J.; Swierstra, S. D. "Make Your Enemies Transparant." 16:00 Uehara, Ryuhei "A Measure of Parallelization for the Lexicographically First Maximal Subgraph Problem" =============16:30 End of the WG'97===================================== ++++++++++++++++++ End of WG'97 programme ++++++++++++++++++++++++++++++++ PROGRAM COMMITTEE =================== G. Ausiello, Roma (I) R. Moehring, Berlin (D), chair H. Bodlaender, Utrecht (NL) M. Nagl, Aachen (D) M. Habib, Montpellier (F) H. Noltemeier, Wuerzburg (D) L. Kirousis, Patras (GR) O. Sykora, Bratislava (SK) L. Kucera, Praha (CR) G. Tinhofer, Munich (D) A. Marchetti-Spaccamela, Roma (I) D. Wagner, Konstanz (D) E. Mayr, Munich (D) P. Widmayer, Zurich (CH) ORGANIZING COMMITTEE ==================== Ewgenij Gawrilow Stephan Hartmann Sabine Marcus Rolf H. Moehring CONTACT ADDRESS =============== Tel.: +49-30-31425728 (Sabine Marcus) Fax: +49-30-31425191 (attention of WG'97) E-Mail: wg97@math.TU-Berlin.DE Subject: INFO URL: http://www.math.TU-Berlin.DE/~wg97 ++++++++++++++++++ Registration form of WG'97 +++++++++++++++++++++++++++++ ********************************************************************** WG'97 June 18 - 20, 1997 - REGISTRATION FORM ********************************************************************** Please complete the form below and return to the WG'97 Workshop office via e-mail (wg97@math.TU-Berlin.DE) with the subject line "REGISTER", or via fax (Fax No. +49-30-31425191) to the attention of WG'97. LAST-NAME: FIRST-NAME: NAME FOR BADGE: COMPANY OR INSTITUTION: MAILING ADDRESS: ZIP: CITY: COUNTRY: TELEPHONE NO: FAX NO.: E-MAIL ADDRESS: DATE OF ARRIVAL [dd.mm.yy]: DATE OF DEPARTURE [dd.mm.yy]: ACCOMMODATION: Accommodation is in single rooms and it is included in the registration fee of DM 500. There are only a few double rooms available that are reserved for participants with an accompanying person. I would like to have a double room for me and an accompanying person. [ ] or [ ] yes no REGISTRATION FEE: 500 DM FEE FOR ACCOMPANYING PERSON: 400 DM PAYMENT: I would like to pay the fees by cheque [ ] or money order [ ] to the following account: to: WG'97 bank: Deutsche Bank, Berlin account: 46 64 710 bank number (BLZ): 100 700 00 or credit card [ ] VISA [ ] MC Attention: If you would like to pay by credit card, please print out --------- this registration form and fax it to us (+49-30-31425191 attention to wg97) with the following data: NUMBER OF CREDIT CARD: EXPIRATION DATE: SIGNATURE: ++++++++++++++++++ End of registration form of WG'97 ++++++++++++++++++++++