19. WG 1993: Utrecht, The Netherlands

Jan van Leeuwen (Ed.): Graph-Theoretic Concepts in Computer Science, 19th International Workshop, WG '93, Utrecht, The Netherlands, June 16-18, 1993, Proceedings. Lecture Notes in Computer Science 790 Springer 1994, ISBN 3-540-57899-4 BibTeX

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 BibTeX
N. W. Holloway, Somasundaram Ravindran, Alan Gibbons: Approximating Minimum Weight Perfect Matchings for Complete Graphs Satisfying the Triangle Inequality. 11-20 BibTeX
Madhav V. Marathe, Venkatesh Radhakrishnan, Harry B. Hunt III, S. S. Ravi: Hierarchical Specified Unit Disk Graphs (Extended Abstract). 21-32 BibTeX

Structural Graph Theory

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

Dynamic Graph Algorithms

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

Structure-Oriented Graph Algorithms

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

Graph Coloring

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

AT-Free and Chordal Graphs

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

Circuits and Nets

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

Graphs and Interconnection Networks

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

Routing and Shortest Paths

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

Graph Embedding and Layout

Koji Nakano: Linear Layouts of Generalized Hypercubes. 364-375 BibTeX
Jianer Chen, Saroja P. Kanchi: Graph Ear Decompositions and Graph Embeddings (Extended Abstract). 376-387 BibTeX
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 BibTeX
Goos Kant, Xin He: Two Algorithms for Finding Rectangular Duals of Planar Graphs. 396-410 BibTeX
Goos Kant: A More Compact Visibility Representation. 411-424 BibTeX