Lecture Notes ni Computer Science Edited yb .G Goos and .J Hartmanis 001 citeroehthparG Concepts ni Computer Science sgnideecorP of the International Workshop WG 80 daB Honnef, June 1980 15-18, Edited yb Hartmut reiemetloN galreV-regnirpS Berlin Heidelberg NewYork 1891 Editorial Board W. Brauer. P. Brinch Hansen D. o Gries - C. Moter o G. SeegmLfller .J Steer • N. Wirth Editor Hartmut Nottemeier Lehrstuhl fQr Informatik ill RWTH Aachen BLichel 29/31 5t00 Aachen Germany AMS Subject Classifications (1979): 68 Et0, 05C15, 05 C38, 68 D90, CR Subject Classifications (1979): 5.32 ISBN 3-540-10291-4 Berlin Heidelberg Springer-Veriag New kroY iSBN 0-387-10291-4 Springer-Verlag NewYork Heidelberg Berlin "yrarbiL of Congress Cataloging ni Publication Main entry Data. under tit{e: Graphtheoretic concepts in computer science. (Lecture notes in computer science; Includes 100). bibliographies and index. .1 Graph theory-Congresses. .2 Electronic data processing-Congresses. .I Noltemeier, Hartmut. .II Series. QA166.G74.51]'.5.81-265.AACRI This work is subject to copyright, All rights are whether reserved, the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcast{rig, reproduction by photocopying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private a use, fee is payable to Verwertungsgese~lschaft Wort, Munich. © by Springer-Vertag Berlin Heidelberg 1891 Printed in Germany Printing and binding: Beltz Offsetdruck, Hemsbach/Bergstr. 2145/3140-543210 PREFACE This volume contains the results of the Workshop WG 80 on 'Graphtheoretic Concepts in Computer Science', which took place at Bad Honnef/Bonn from June 15 to 18, 1980. WG 80 was the sixth Workshop on this topic since 1975, when the first conference, which centered around a tutorial on graph languages, was organized by U. Pape in cooperation with ACM in Berlin. The present form of this Workshop WG - where a limited number of invited participants can concentrate their efforts upon problems in this field and are able to communicate in an inti- mate atmosphere very personally - was first established at WG 76 in G~ttingen .H( Noltemeier) and was continued very sucessfully in Linz (77; J. M~hlbacher), Erlangen (78; H.J. Schneider), Berlin (79; U. Pape). Today this workshop WG has become a well known annual meeting for all those scientists, who are working in the field of Graphtheoretic Concepts in Computer Science. These concepts seem to play an increasingly important role in Computer Science as well as in a huge variety of applications, but are still far from being a standard topic in teaching Computer Science. The workshop WG 80 was attended by some fifty invited scientists from 11 countries all over the world and was for the first time co-sponsored by the European Association for Theoretical Computer Science-EATCS. The scientific program consisted of 34 contributions on the following topics: graptheoretic models, data structures, algorithms on graphs, complexity, graph grammars, systems for graph manipulations, conceptional and algorithmic aspects of data base design, net theory, graph theory as well as combinatorial and optimization problems, applications. VI Partial support of the Stiftung Volkswagenwerk is very gratefully acknowledged. i am very indebted to all participants of the workshop, especially to the authors and referees; a lot of exciting results and questions at WG 80 surely will be the best guarantee for a successful continuation of WG. The contributions~ which were accepted by the referees, are in the order of the talks given at the Workshop. Finally I have to thank very cordially all my fellows and staff members of Lehrstuhl fur Informatik III at Aachen~ who did their best for a successful meeting. Aachen, October 1980 Hartmut Noltemeier CONTENTS H. Maurer THE POST-OFFICE PROBLEM AND RELATED QUESTIONS H. Nishio SERIES OF GRAPHS GENERATED BY RATIONAL MACHINES 20 K.-U. Witt ON LINEARIZING GRAPHS 32 H.J. Schneider SET-THEORETIC CONCEPTS IN PROGRA~iMING LANGUAGES 42 AND THEIR IMPLEMENTATION M. Nagl GRAPH REWRITING AND AUTOMATIC, MACHINE-INDEPEN- 55 DENT PROGRAM OPTIMIZATION H.J. Ludwigs PROPERTIES OF ORDERED GRAPH GRAMmaRS 70 J.L. Bentley/Th. Ottmann THE POWER OF A ONE-DIMENSION~ VECTOR OF PROCESSORS 80 .K Mehlhorn A NEW DATA STRUCTURE FOR REPRESENTING SORTED LISTS 90 .G Tinhofer ON THE USE OF SOME ALMOST SURE GRAPH PROPERTIES 1t3 H. Noltemeier ON A GENERALIZATION OF HEAPS 127 M. Sc~nitzler GRAPH GRAMMARS AND THE COMPLEXITY GAP IN THE 137 ISOMORPHISM PROBLEM FOR ACYCLIC DIGRAPHS A.L. RosenSerg ISSUES IN THE STUDY OF GRAPH EMBEDDINGS 150 IV .C Batini/ .A D~Atri SCHEMA HYPERGRAPHS: A FORMALISM TO INVESTIGATE 177 LOGICAL DATA BASE DESIGN .P Kandzia/ .M Mangelmann THE USE OF TP~_NSITIVELY IRREDUCIBLE KERNELS OF 195 FULL FAMILIES OF FUNCTIONAL DEPENDENCIES IN LOGICAL DATA BASE DESIGN .G Ausiello/ A. D~Atri/ D. Sated GRAPH ALGORITHMS FOR THE SYNTHESIS AND MANIPULATION 212 OF DATA BASE SCHEMES Yh. Ottmann/ H.-W. Six/ ,D Wood THE ANALYSIS OF SEARCH TREES: A SURVEY 234 .W-~.H Six A FP~hMEWORK FOR DATA STRUCTURES 250 .G Schmidt INVESTIGATING PROGRAMS IN TERMS OF PARTIAL GRAPHS 268 .S Even/ .Y Yaoobi AN OBSERVATION CONCERNING THE COMPLEXITY OF PROBLEMS 270 WITH FEW SOLUTIONS AND ITS APPLICATION TO CRYPTO- GRAPHY .B Monien/ Z.H. Sudborough BOUNDING THE BANDWIDTH OF NP-COMPLETE PROBLEMS 279 I.H, Sudborough THE COMPLEXITY OF PATH PROBLEMS IN GRAPHS AND 293 PATH SYSTEMS OF BOUNDED BANDWIDTH H.-J, Kreowski A COMPARISION BETWEEN PETRI--NETS AND GRAPH 306 GRA/V~RS .W ~eisig A GRAPH GI~X.MMAR REPRESENTATION OF NONSEQUENTIAL 318 PROCESSES IIV J. Perl/ J. Ebert REACHABILITY HOMOMORPHISMS ON NETS 326 B. Mahr A BIRD'S-EYE VIEW TO PATH PROBLEMS 335 P. Brucker THE CHINESE POSTMAN PROBLEM FOR MIXED GRAPHS 354 .O Vornberger ALTERNATING CYCLE COVERS AND PATHS 367 .P Lduahli GENERATING ALL PLANAR O-,I-,2-,3-CONNECTED 379 GRAPHS H. Hamacher OPTIMAL (s,t)-CUTS 383 .U Derigs F-FACTORS, PERFECT MATCHINGS AND RELATED 388 CONCEPTS AUTHORS Prof. A. d~Atri~ Istituto di Automatica, Unversit~ di Roma, Via Eudossiana 18, 00184 Roma, Italy Prof. Dro G. Ausiellon Istituto di Automaticar Universit~ di Roma, Via Eudossiana 18, 00184 Roma, Italy Prof. C. Batini~ Istituto di Automatica, Universit~ di Roma, Via Eudossiana 18, 00184 Roma, Italy Dr. J.L. B entley~ Department of Computer Science and Mathematics, Carnegie-Mellon University, Pittsburgh, Pennsylvania 15213, USA Profo Dro P° Brucker, Fachbereich IV der Universit~t Oldenburg, Ammerl~nder Heerstr. 67-69, Postfach 2503 2900 Oldenburg, W. Germany Dro U° Deriqs; Seminar f~r Allgemeine und Industrielle Betriebswirtschaftslehre, Universit~t zu K~in, Albertus- Magnus-Platz, 5000 K~in 41, W. Germany Dro J. Ebert~ Universit~t Osnabr~ck~ Fachbereich 5, Postfach 44691 4500 OsnabrOck, W. Germany Profo Dr. So Even~ Technion-Israel Institute of Technology, Department of Computer Science, Haifa, Israel Dr. H. Hamacher, Mathematisches Institut der Universit~t zu K~in, Weyertal 86-90, 5000 K~in 41, W. Germany Prof. Dr. P. Kandzia~ Institut f~r !nformatik und Praktische Mathematik, Christian-Albrechts-Universit~t Kiel, Olshausenstr. 40-60, 2300 Kiel ,I W. Germany Dr. H.-J. Kreowski, Institut f~r Software und Theoretische Informatik, Fachbereich 20 der TU Berlin, Otto-Suhr-Allee 18/20, 1000 Berlin 10, W. Germany Prof. Dr. P~ L~uchli~ Institut fur Informatik, ETH-Zentrum 8092 Zurich, Switzerland JX H. J. Ludwigs, Universit~t Dortmund, Informatikrechner- Betriebsgruppe, Postfach 500500, 4600 Dortmund 50, W. Germany Dr. B. Mahr, Institut fur Software und Theoretische Informatik, Fachbereich 20 der TU Berlin, Otte-Suhr- Allee 18/20, 1OOO Berlin 10, W. Germany M. Mangelmann, Institut fur Informatik und Praktische Mathematik, Christian-Alhrechts-UniversitMt Kiel, OlshausenstraBe 40-60, 2300 Kiel ,I W. Germany Prof. Dr. H. Maurer, Institut fur Informationsverarbeitung, TU Graz, Steyrergasse 17, 8010 Graz, Austria Prof. Dr. K. Mehlhorn, Fachbereich 10 der Unversit~t des Saarlandes, Angewandte Mathematik und Informatik, Im Stadtwald, 6600 SaarbrUcken, W. Germany Prof. Dr. B. Monfen, Fachbereich 17 der Universit~t - Gesamthochschule - Paderborn, Warburger Str. 100, Postfach 1621, 4790 Paderborn, W. Germany Prof. Dr. M. Nagl, Seminar fur Informatik, Erziehungs- wissenschaftliche Hochschule Koblenz, Rheinau 3-4, 5400 Koblenz, W. Germany Dr. H. Nishio, Department of Biophysics, Faculty of Science, Kyoto University, Kyoto, Japan Prof. Dr. H. Noltemeier, Lehrstuhl fur Informatik III, RWTH Aachen, BUchel 29/31, 51OO Aachen, W. Germany Prof. Dr. Th. Ottmann, Institut ffir Angewandte In- formatik und Formale Beschreibungsverfahren der Uni- versit~t Karlsruhe, Kollegium am Schloss, Bau IV, 7500 Karlsruhe ,I W. Germany Prof. Dr. J. Perl, Universit~t OsnabrUck, Fachbereich 5, Postfach 4469, 4500 OsnabrUck, W. Germany Dr. W. Reisi~ Lehrstuhl fur Informatik II, RWTH Aachen, B~chel 29/3], 5100 Aachen, W° Germany Prof. Dr. A.L0 Rosenberg, Mathematical Sciences Department, IBM Research Center, P.O. Box 218, Yorktown Heights, NY IO598t USA Prof. D. Sacc~ CRAI, Via Modig!iani, C. da. S. Agostino, 87036 Roges di Rende {CS) ~ Italy PriV. Doz. Dr~ G. Schmidt, Institut f0r Informatik der TU MHnchen, Postfach 202420, 8000 M~nchen 2, W. Germany Prof. Dr. H.J. Schneider, Lehrstuhl fHr Programmier- und Dialogsprachen, Universit~t Erlangen-NHrnberg, Martensstr. ,3 8520 Erlangen, W. Germany Dipl. Math. M. Schnitzler, Lehrstuhl f~r Informatik III, RK~H Aachen, B~chel 29/31, 5!O0 Aachen, W. Germany Dr. H.-W. Six~ Institut fHr Angewandte Informatik und Formale Beschreibungsverfahren der Universit~t Karlsruhe, Kollegium am Schloss, Bau IV, 7500 Karlsruhe ,I W. Germany Prof. Dr° I.H. Sudboroug_hh, EE and CS Department, North- western University, Evanston, IL 60201, USA Prof. Dr. G. Tinhoferr Institut fur Mathematik der TU M~nchenf Arcisstr. 21, 8000 M~nchen ,2 W. Germany Dr. O. Vornber~, Department of Electrical Engineering and Computer Science~ University of Californial Berkeley, Ca.94720, USA ~i. Math. K.~U. Witt, Lehrstuhl f~r Informatik III, RWTH Aachen, B~chel 29/31, 5100 Aachen, W. Germany Prof. Dr. Do Wood, Unit of Computer Science, Mc Master University, Hamilton, Ontario, L8S4K1, Canada Y. Yacobit Technion --Israel Institute of Technology, Department of Electrical Engineering, Haifa, Israel