19. WG 1993: Utrecht, The Netherlands

Hard Problems on Classes of Graphs

• Sotiris E. Nikoletseas, Paul G. Spirakis:
  Near-Optimal Dominating Sets in Dense Random Graphs in Polynomial Expected Time. 1-10
  
• N. W. Holloway, Somasundaram Ravindran, Alan Gibbons:
  Approximating Minimum Weight Perfect Matchings for Complete Graphs Satisfying the Triangle Inequality. 11-20
  
• Madhav V. Marathe, Venkatesh Radhakrishnan, Harry B. Hunt III, S. S. Ravi:
  Hierarchical Specified Unit Disk Graphs (Extended Abstract). 21-32
  

Structural Graph Theory

• Egon Wanke:
  Bounded Tree-Width and LOGCFL. 33-44
  
• Hans L. Bodlaender:
  On Reduction Algorithms for Graphs with Small Treewidth. 45-56
  
• Martin Charles Golumbic, Haim Kaplan, Ron Shamir:
  Algorithms and Complexity of Sandwich Problems in Graphs (Extended Abstract). 57-69
  

Dynamic Graph Algorithms

• Alberto Marchetti-Spaccamela, Umberto Nanni, Hans Rohnert:
  On-line Graph Algorithms for Incremental Compilation. 70-86
  
• Paola Alimonti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Xavier Messeguer:
  Average Case Analysis of Fully Dynamic Connectivity for Directed Graphs. 87-98
  
• Zoran Ivkovic, Errol L. Lloyd:
  Fully Dynamic Maintenance of Vertex Cover. 99-111
  
• Hans L. Bodlaender:
  Dynamic Algorithms for Graphs with Treewidth 2. 112-124
  

Structure-Oriented Graph Algorithms

• Andreas Brandstädt, Heinz-Jürgen Voss:
  Short Disjoint Cycles in Graphs with Degree Constraints. 125-131
  
• Koichi Wada, Kimio Kawaguchi:
  Efficient Algorithms for Tripartitioning Triconnected Graphs and 3-Edge-Connected Graphs. 132-143
  
• Zbigniew Lonc:
  Toward a Solution of the Holyer's Problem. 144-152
  
• George Havas, Bohdan S. Majewski, Nicholas C. Wormald, Zbigniew J. Czech:
  Graphs, Hypergraphs and Hashing. 153-165
  

Graph Coloring

• Ludek Kucera:
  Coloring k-Colorable Graphs in Constant Expected Parallel Time. 166-176
  
• Ingo Schiermeyer:
  Deciding 3-Colourability in Less Than O(1.415^n) Steps. 177-188
  
• Klaus Jansen:
  A Rainbow About T-Colorings for Complete Graphs. 189-199
  
• Nai-Wei Lin:
  Approximating the Chromatic Polynomial of a Graph. 200-210
  

AT-Free and Chordal Graphs

• Derek G. Corneil, Stephan Olariu, Lorna Stewart:
  Asteroidal Triple-Free Graphs. 211-224
  
• Elias Dahlhaus:
  The Parallel Complexity of Elimination Ordering Procedures. 225-236
  
• Andreas Brandstädt, Feodor F. Dragan, Victor Chepoi, Vitaly I. Voloshin:
  Dually Chordal Graphs. 237-251
  

Circuits and Nets

• Ingo Wegener:
  The Size of Reduced OBDDs and Optimal Read-once Branching Programs for Almost all Boolean Functions. 252-263
  
• Jörg Desel:
  Regular Marked Petri Nets. 264-275
  
• Javier Esparza, Bernhard von Stengel:
  The Asynchronous Committee Meeting Problem. 276-287
  

Graphs and Interconnection Networks

• Juraj Hromkovic, Ralf Klasing, Elena Stöhr:
  Gossiping in Vertex-Disjoint Path Mode in Interconnection Networks. 288-300
  
• Sabine R. Öhring, Sajal K. Das:
  The Folded Petersen Network: A New Versatile Multiprocessor Interconnection Topology. 301-314
  
• Jacques E. Boillat:
  Fast Load Balancing in Cayley Graphs and in Circuits. 315-326
  

Routing and Shortest Paths

• Farhad Shahrokhi, László A. Székely:
  Concurrent Flows and Packet Routing in Cayley Graphs (Preliminary Version). 327-337
  
• Evangelos Kranakis, Danny Krizanc, S. S. Ravi:
  On Multi-Label Linear Interval Routing Schemes (Extended Abstract). 338-349
  
• S. Haldar:
  An `All Pairs Shortest Path' Distributed Algorithm Using 2n² Messages. 350-363
  

Graph Embedding and Layout

• Koji Nakano:
  Linear Layouts of Generalized Hypercubes. 364-375
  
• Jianer Chen, Saroja P. Kanchi:
  Graph Ear Decompositions and Graph Embeddings (Extended Abstract). 376-387
  
• Farhad Shahrokhi, László A. Székely, Ondrej Sýkora, Imrich Vrto:
  Improving Bounds for the Crossing Numbers on Surfaces of Genus g. 388-395
  
• Goos Kant, Xin He:
  Two Algorithms for Finding Rectangular Duals of Planar Graphs. 396-410
  
• Goos Kant:
  A More Compact Visibility Representation. 411-424