Graph-Theoretic Concepts in Computer Science : 25th International Workshop, WG'99, Ascona, Switzerland, June 17-19, 1999 Proceedings

by Widmayer, P.; Neyer, G.; Eidenbenz, S.; Goos, G.; Hartmanis, J.; Leeuwen, J. Van

• ISBN13: 9783540667315
• ISBN10: 3540667318
• Format: Paperback
• Copyright: 1999-01-01
• Publisher: Springer Verlag
• More Book Details
• Purchase Benefits

Summary

This book constitutes the refereed proceedings of the 25th International Workshop on Graph-Theorie Concepts in Computer Science WG'99, held at the Centre Stefano Frascini on Monte Verita, Ascona, Switzerland in June 1999. The 33 revised full papers presented together with four invited contributions were carefully reviewed and selected from 64 papers submitted. The papers provide a wealth of new results for various graph classes, graph computations, graph algorithms and graph-theoretical applications in a variety of fields.

Table of Contents

Invited Lecture: Silver Graphs: Achievements and New Challenges	p. 1
Invited Lecture: Online Algorithms: A Studyof Graph-Theoretic Concepts	p. 10
Invited Lecture: Discrete Optimization Methods for Packing Problems in Two and Three Dimensions - With Applications in the Textile and
Car Manufacturing Industries	p. 27
Informatica, Scuola, Communita: Uno Sguardo dall' Occhio del Ciclone	p. 29
Proximity-Preserving Labeling Schemes and Their Applications	p. 30
Euler is Standing in Line	p. 42
Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2	p. 55
ComplexityClassification of Some Edge Modification Problems	p. 65
On Minimum Diameter Spanning Trees under Reload Costs	p. 78
Induced Matchings in Regular Graphs and Trees	p. 89
Mod-2 Independence and Domination in Graphs	p. 101
NLC2-Decomposition in Polynomial Time	p. 110
On the Nature of Structure and Its Identification	p. 122
On the Clique-Width of Perfect Graph Classes	p. 135
An Improved Algorithm for Finding Tree Decompositions of Small Width	p. 148
Efficient Analysis of Graphs with Small Minimal Separators	p. 155
Generating All the Minimal Separators of a Graph	p. 167
Two Broadcasting Problems in FaultyHypercubes	p. 173
Routing Permutations in the Hypercube	p. 179
An Optimal Fault-Tolerant Routing for Triconnected Planar Graphs	p. 191
Optimal Irreversible Dynamos in Chordal Rings	p. 202
Recognizing Bipartite Incident-Graphs of Circulant Digraphs	p. 215
Optimal Cuts for Powers of the Petersen Graph	p. 228
Dihamiltonian Decomposition of Regular Graphs with Degree Three	p. 240
Box-Rectangular Drawings of Plane Graphs	p. 250
A Multi-Scale Algorithm for Drawing Graphs Nicely	p. 262
All Separating Triangles in a Plane Graph Can Be Optimally "Broken" in Polynomial Time	p. 278
Linear Orderings of Random Geometric Graphs	p. 291
Finding Smallest Supertrees Under Minor Containment	p. 303
Vertex Cover: Further Observations and Further Improvements	p. 313
On the Hardness of Recognizing Bundles in Time Table Graphs	p. 325
Optimal Solutions for FrequencyAssignment Problems via Tree Decomposition	p. 338
Fixed-Parameter Complexity of ¿-Labelings	p. 350
Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)-Free Graphs	p. 364
On Claw-Free Asteroidal Triple-Free Graphs	p. 377
Vertex Partitioning of Crown-Free Interval Graphs	p. 391
Triangulated Neighbourhoods in C4-Free Berge Graphs	p. 402
Author Index	p. 413
Table of Contents provided by Publisher. All Rights Reserved.