Graph-Theoretic Concepts in Computer Science

25th International Workshop, WG'99, Ascona, Switzerland, June 17-19, 1999 Proceedings

432 Seiten, Taschenbuch

Kurzbeschreibung des Verlags

Silver Graphs: Achievements and New Challenges.- Online Algorithms: A Study of Graph-Theoretic Concepts.- Discrete Optimization Methods for Packing Problems in Two and Three Dimensions - With Applications in the Textile and Car Manufacturing Industries.- Informatica, Scuola, Communità: Uno Sguardo dall' Occhio del Ciclone.- Proximity-Preserving Labeling Schemes and Their Applications.- Euler Is Standing in Line.- Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2.- Complexity Classification of Some Edge Modification Problems.- On Minimum Diameter Spanning Trees under Reload Costs.- Induced Matchings in Regular Graphs and Trees.- Mod-2 Independence and Domination in Graphs.- NLC2-Decomposition in Polynomial Time.- On the Nature of Structure and Its Identification.- On the Clique-Width of Perfect Graph Classes.- An Improved Algorithm for Finding Tree Decompositions of Small Width.- Efficient Analy sis of Graphs with Small Minimal Separators.- Generating All the Minimal Separators of a Graph.- Two Broadcasting Problems in FaultyHypercubes.- Routing Permutations in the Hypercube.- An Optimal Fault-Tolerant Routing for Triconnected Planar Graphs.- Optimal Irreversible Dy namos in Chordal Rings.- Recognizing Bipartite Incident-Graphs of Circulant Digraphs.- Optimal Cuts for Powers of the Petersen Graph.- Dihamiltonian Decomposition of Regular Graphs with Degree Three.- Box-Rectangular Drawings of Plane Graphs.- A Multi-Scale Algorithm for Drawing Graphs Nicely.- All Separating Triangles in a Plane Graph Can Be Optimally "Broken" in Poly nomial Time.- Linear Orderings of Random Geometric Graphs.- Finding Smallest Supertrees Under Minor Containment.- Vertex Cover: Further Observations and Further Improvements.- On the Hardness ofRecognizing Bundles in Time Table Graphs.- Optimal Solutions for Frequency Assignment Problems via Tree Decomposition.- Fixed-Parameter Complexity of ?-Labelings.- Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)-Free Graphs.- On Claw-Free Asteroidal Triple-Free Graphs.- Vertex Partitioning of Crown-Free Interval Graphs.- Triangulated Neighbourhoods in C 4-Free Berge Graphs.

• Reihe: Lecture Notes in Computer Science
• Themen: Informatik und Informationstechnologie Informatik Theoretische Informatik
• ISBN: 9783540667315
• Sprache: Englisch
• Erscheinungsdatum: 27.10.1999
• Größe: 235 x 155 mm
• Verlag: Springer
• Herausgegeben von: Peter Widmayer, Gabriele Neyer, Stephan Eidenbenz