WORKSHOP: WG'93 Graph-theoretic Concepts

[Jan van Leeuwen]

L.S.
Attached is the complete program of WG'93, the 19th International Workshop
on GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE. The Workshop is held
June 16-18, 1993 near Utrecht, The Netherlands.

To register, simply send a message or fax to: go...@cs.ruu.nl, mar...@cs.ruu.nl,
or j...@cs.ruu.nl (preferably not later than June 11). Our fax: +31-30-513791.
There is no penalty for late registration.

A LateX version of the program is available on request.
We look forward to seeing you at WG'93.

Sincerely
Jan van Leeuwen
(Organizational Chairman WG'93)

email: j...@cs.ruu.nl
fax : +31-30-513791

=============================================================================

19th International Workshop on
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG'93)

Utrecht (NL), June 16-18, 1993

The 19th International Workshop on Graph-Theoretic Concepts in Computer
Science (WG'93) will be held near Utrecht (The Netherlands), June 16-18 (1993),
in the conference facilities of the ``National Sports Centre PAPENDAL''.
This year's WG is sponsored by ESPRIT Basic Research Action 7141 (Project
ALCOM II).

TECHNICAL PROGRAM

TUESDAY, June 15, 1993

19.30-21.30 Reception at `Papendal'.

WEDNESDAY, June 16, 1993

Session 1. (Chairman: Jan van Leeuwen)

9.00 Near-Optimal Dominating Sets in Dense Random Graphs in Polynomial
expected Time
S.E. Nikoletseas (Patras University) and P.G. Spirakis (Computer
Technology Institute and Patras University).
9.30 Approximating Minimum Weight Perfect Matchings, for Complete Graphs
Satisfying the Triangle Inequality, with a Logarithmic Performance
Ratio is in NC
S. Ravindran, N.W. Holloway and A.M. Gibbons (University of Warwick).
10.00 Hierarchically Specified Unit Disk Graphs
M.V. Marathe, V. Radhakrishnan, H.B. Hunt III and S.S. Ravi (University
at Albany-SUNY).
10.30 Break

Session 2. (Chairman: Rolf H. Moehring)

11.00 Bounded Treewidth and LOGCFL
E. Wanke (GMD, Sankt Augustin).
11.30 On Reduction Algorithms for Graphs with Small Treewidth
H.L. Bodlaender (Utrecht University).
11.45 Algorithms and Complexity of Sandwich Problems in Graphs
M.C. Golumbic (IBM Israel Scientific Center/Haifa and Bar-Ilan
University), H. Kaplan and R. Shamir (Tel Aviv University).
12.15 Lunch

Session 3. (Chairman: Ernst Mayr)

14.00 On-line Graph Algorithms for Incremental Compilation
A. Marchetti-Spaccamela (Universita di Roma ``La Sapienza''/ICSI
Berkeley), U. Nanni (Universita di L'Aquila/ICSI Berkeley) and H.
Rohnert (Siemens AG, Muenchen).
14.15 Average Case Analysis of Fully Dynamic Connectivity for Directed Graphs
P. Alimonti, S. Leonardi, A. Marchetti-Spaccamela (Universita di
Roma ``La Sapienza'') and X. Messeguer (Universitat Politecnica de
Catalunya, Barcelona).
14.45 Fully Dynamic Maintenance of Vertex Cover
Z. Ivkovic and E.L. Lloyd (University of Delaware, Newark).
15.15 Break

Session 4. (Chairman: Hartmut Noltemeier)

15.45 Dynamic Algorithms for Graphs with Treewidth 2
H.L. Bodlaender (Utrecht University).
16.15 Short Disjoint Cycles in Graphs with Degree Constraints
A. Brandstaedt (Universitaet Duisburg) and H-J. Voss (TU Dresden).
16.30 Efficient Algorithms for Tripartitioning Triconnected Graphs and
3-Edge-Connected Graphs
K. Wada and K. Kawaguchi (Nagoya Institute of Technology).
17.00 Towards a Solution of Holyer's Problem
Z. Lonc (Warsaw University of Technology).

Thursday, June 17, 1993
Session 5. (Chairman: Gottfried Tinhofer)

8.45 Graphs, Hypergraphs and Hashing
G. Havas, B.S. Majewski (University of Queensland), N.C. Wormald
(University of Melbourne) and Z.J. Czech (Silesia University of
Technology).
9.00 Coloring k-Colorable Graphs in Constant Expected Parallel Time
L. Kucera (Charles University, Prague).
9.30 Deciding 3-Colourability in O(1.4293^n) Steps
I. Schiermeyer (RWTH Aachen).
9.45 A Rainbow about T-Colorings for Complete Graphs
K. Jansen (Universitaet Trier).
10.00 Approximating the Chromatic Polynomial of a Graph
Nai-Wie Lin (University of Arizona).
10.30 Break

Session 6. (Chairman: Gunther Schmidt)

11.00 The Linear Structure of Graphs: Asteroidal Triple-Free Graphs
D.G. Corneil (University of Toronto), S. Olariu (Old Dominion University,
Norfolk) and L. Stewart (University of Alberta, Edmonton).
11.30 The Parallel Complexity of Elimination Ordering Procedures
E. Dahlhaus (University of Sydney).
12.00 Maximum Neighbourhood Orderings of Graphs
A. Brandstaedt (Universitaet Duisburg), F.F. Dragan, V. Chepoi and V.I.
Voloshin (Chisinau).
12.30 Lunch

Session 7. (Chairman: Manfred Nagl)

14.00 The Size of Reduced OBDDs and Optimal Read-once Branching Programs
for Almost All Boolean Functions
I. Wegener (Universitaet Dortmund).
14.30 Regular Marked Petri Nets
J. Desel (TU Muenchen).
15.00 Excursion.

Friday, June 18, 1993
Session 8. (Chairman: Juray Wiedermann)

8.45 The Asynchronous Committee Meeting Problem
J. Esparza (Universitaet Hildesheim) and B. von Stengel (Universitaet
der Bundeswehr Muenchen).
9.00 Gossiping in Vertex-disjoint Paths Mode in Interconnection Networks
J. Hromkovic, R. Klasing and E.A. Stoehr (Universitaet Paderborn).
9.30 The Folded Petersen Network: a New Versatile Multiprocessor
Interconnection Topology
S. Oehring (Universitaet Wuerzburg) and S. Das (University of North
Texas, Denton).
10.00 Fast Load Balancing in Cayley Graphs and in Circuits
J.E. Boillat (Universitaet Bern).
10.30 Break

Session 9. (Chairman: Paul Spirakis)

11.00 Integral Concurrent Flows and Packet Routing
F. Shahrokhi (University of North Texas, Denton) and L.A. Szekely
(Eotvos University, Budapest and University of New Mexico, Albuquerque).
11.30 On Multi-Label Linear Interval Routing Schemes
E. Kranakis, D. Krizanc (Carleton University, Ottawa) and S.S. Ravi
(University at Albany-SUNY).
12.00 An `All Pairs Shortest Paths' Distributed Algorithm using 2n^{2}
messages
S. Haldar (Utrecht University).
12.30 Lunch

Session 10. (Chairman: Roberto Tamassia)

14.00 Linear Layouts of Generalized Hypercubes
K. Nakano (Advanced Research Laboratory, Hitachi Ltd).
14.15 Graph Ear Decompositions and Graph Embeddings
J. Chen and S.P. Kanchi (Texas A&M University).
14.30 The Crossing Number of a Graph on a Compact 2-Manifold
F. Shahrokhi (University of North Texas, Denton), O. Sykora (Slovak
Academy of Sciences, Bratislava), L.A. Szekely (Eotvos University,
Budapest), and I. Vrto (Slovak Academy of Sciences, Bratislava).
15.00 Two Algorithms for Finding Rectangular Duals of Planar Graphs
G. Kant (Utrecht University) and Xin He (SUNY at Buffalo).
15.30 A More Compact Visibility Representation
G. Kant (Utrecht University).
16.00 Tea/End of Workshop

PROGRAM COMMITTEE: Jan van Leeuwen (chairman, Utrecht), Ernst W. Mayr
(Frankfurt/Muenchen), Rolf H. Moehring (Berlin), Manfred Nagl (Aachen),
Hartmut Noltemeier (Wuerzburg), Gunther Schmidt (Muenchen), Paul Spirakis
(Patras), Roberto Tamassia (Providence), Gottfried Tinhofer (Muenchen), and
Juray Wiedermann (Bratislava).

PROCEEDINGS. The official proceedings of WG'93 will be published in the
series Lecture Notes in Computer Science of Springer-Verlag in the course of
1993. Participants are entitled to a copy of the proceedings as part of their
registration.

LOCATION. The Workshop will be held in the conference facilities of the
``National Sports Centre PAPENDAL'' of the Dutch National Sports Federation.
The conference centre is located in a beautifully forested area near the city
of Arnhem, some 30 miles east of Utrecht. It features excellent facilities
for recreational sports (golf, swimming, tennis, and so on) and pleasant
surroundings. The Workshop participants will get free access to all sports
facilities as part of their registration. The address of PAPENDAL is:

National Sports Centre ``PAPENDAL''
Papendallaan 3 (entrance Amsterdamseweg)
P.O. Box 484
6800 AL Arnhem
The Netherlands
Telephone: +31-8308-37911, Fax: +31-8308-21853

The conference centre is easily reached by public transportation and by car
(plenty of free parking space is available). Detailed information on how to
reach PAPENDAL will be provided with the acknowledgement of your registration.

REGISTRATION FOR WG93. In order to register for WG'93, SIMPLY SEND AN EMAIL
MESSAGE OR A FAX (preferably not later than June 11) to:

WG'93 secretary: Margje Punt (mar...@cs.ruu.nl),
WG'93 assistant: Goos Kant (go...@cs.ruu.nl),
or to the
WG'93 chairman : Prof Jan van Leeuwen (j...@cs.ruu.nl)

Fax: +31-30-513791

Dept of Computer Science
University of Utrecht
Padualaan 14
3584 CH Utrecht
The Netherlands

The registration fee for the Workshop is Dfl 340,- (this is approx.
DM 305,- or US $ 190.- or equivalent amount in any other common currency).
For Ph.D. students a special reduced registration fee of Dfl 290,- (this is
approx. DM 260,- or US $ 160.- or equivalent in any other common currency)
can be offered, provided they attach a letter of reference from their
advisor.
Accompanying persons who participate in all nonscientific activities of
the workshop can be registered at half price.
The registration fee includes the reception on Tuesday evening (June 15),
registration materials, meals and refreshments during the Workshop, the
excursion (planned to be on rental bicycle), a copy of the final proceedings,
and use of all sports facilities at PAPENDAL. The registration fee has to be
paid in advance by sending a check for the required amount to the
organizational chairman (make checks payable to `Workshop WG 93') or by
transferring it by bank to account 46.21.89.813 (ABN-AMRO Bank, Zeist, The
Netherlands) of `Workshop WG 93'/Prof Jan van Leeuwen. Add Dfl 10,-
(equivalently DM 9,- or US $ 6.-) to the registration fee when paying by
foreign check to defray bank charges. Refund requests will be honored until
June 7, 1993.

HOTEL. The participants of WG'93 will be housed in a simple but convenient
hotel (Hotel II) on the PAPENDAL complex. Room rates are Dfl 65,- (approx. DM
58,- or US $ 37.-) per day for a single room, and Dfl 47.50 (approx. DM 43,-
or US\$ 27.-) per person per day for a double.
Room rates include breakfast and taxes. If you wish, you can book
accommodation in the adjacent, more luxurious `Hotel III' on the complex
instead (room rates for Hotel III are Dfl 105,- for a single and Dfl 65,- for
a double room, per person per day). The hotel accepts payments in cash, by
Eurocheque, by Eurocard and by American Express card.

TO REQUEST HOTEL ACCOMODATION, simply send an email message or a fax
(preferably not later than June 11) to mar...@cs.ruu.nl, go...@cs.ruu.nl, or
the organizational chairman: j...@cs.ruu.nl (all at the above address).

Reservations will be handled on a first-come first-serve basis. Note that the
Workshop organization only acts as an intermediary and takes no responsibility
for your further contacts with the hotel. (Very late bookings should be
arranged directly with PAPENDAL. Mention that you are with the WG Workshop.)

REGISTRATION AND RECEPTION. The WG-registration desk will be open at PAPENDAL
on Tuesday, June 15, 1993 from 19.00 until 21.00 and on every subsequent
day of the Workshop from 8.30 until noon. Tuesday, June 15, 1993 there will be
a welcoming reception from 19.30 until 21.30. The hotel desk provides the
necessary PAPENDAL-information, the meal-tickets to use etcetera at check-in.
If you wish to have dinner at PAPENDAL on the evening of June 15 (between
17.30 and 19.00!), indicate this when you register (it is not included in the
standard Workshop arrangement).

FURTHER INFORMATION. Participants arriving by airplane at Amsterdam Airport
should take a train at the airport to ARNHEM. (Follow the signs `To the
Trains' in the arrival hall, buy a ticket to Arnhem, and the relaxed
train-ride will lead you through a nice variety of Dutch landscapes. PAPENDAL
is only a few miles from the Arnhem Station and easily reached by bus or cab.)
Participants arriving by train should likewise travel to Arnhem. For
participants arriving by car, PAPENDAL is situated close to the
Utrecht-Arnhem (A12/E35) freeway. Driving on the A12/E35 from Utrecht to
Arnhem, take the `Oosterbeek-Wolfheze-Arnhem Centrum-Hoge Veluwe' exit, turn
right on the N224 and PAPENDAL is reached in a few minutes from there.
Driving on the A12/E35 from Arnhem to Utrecht, take the
`Oosterbeek-Wolfheze-Ede Oost' exit, turn left on the N224 and continue to the
exit PAPENDAL. Instructions on how to reach PAPENDAL from various other
directions will be provided with the acknowledgement of your registration.

PAPENDAL is located in one of the most scenic areas of The Netherlands. The
National Park `De Hoge Veluwe' is within easy distance, as are several other
touristic attractions. For further information, contact:
mar...@cs.ruu.nl, go...@cs.ruu.nl, or j...@cs.ruu.nl

See you at WG'93!

===========================PLEASE DISTRIBUTE====================================