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

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

Last update Sun May 19 23:44:21 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page