Graph-Theoretic Concepts in Computer Science 22nd International Workshop, WG '96, Cadenabbia, Italy, June 12-14, 1996, Proceedings /

• Corporate Author: SpringerLink (Online service)
• Other Authors: D'Amore, Fabrizio (Editor, http://id.loc.gov/vocabulary/relators/edt), Franciosa, Paolo Giulio (Editor, http://id.loc.gov/vocabulary/relators/edt), Marchetti-Spaccamela, Alberto (Editor, http://id.loc.gov/vocabulary/relators/edt)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1997.
• Edition: 1st ed. 1997.
• Series: Lecture Notes in Computer Science, 1197
• Subjects: Computers.; Applied mathematics.; Engineering mathematics.; Algorithms.; Data structures (Computer science).; Computer graphics.; Theory of Computation.; Applications of Mathematics.; Algorithm Analysis and Problem Complexity.; Computation by Abstract Devices.; Data Structures.; Computer Graphics.

This book constitutes the carefully refereed post-proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG '96, held in Cadenabbia, Italy, in June 1996. The 30 revised full papers presented in the volume were selected from a total of 65 submissions. Thi...

Table of Contents:

• Hypergraphs and decision trees
• Improved approximations of independent dominating set in bounded degree graphs
• A new characterization of P 4-connected graphs
• Node rewriting in hypergraphs
• On ?-partitioning the n-cube
• Embedding complete binary trees in product graphs
• Clique and anticlique partitions of graphs
• Optimal parallel routing in star graphs
• Counting edges in a dag
• Closure properties of context-free Hyperedge Replacement Systems
• Upward drawings of search trees
• More general parallel tree contraction: Register allocation and broadcasting in a tree
• System diagnosis with smallest risk of error
• Efficient algorithms for shortest path queries in planar digraphs
• LexBFS-orderings and powers of graphs
• Efficient Union-Find for planar graphs and other sparse graph classes
• Switchbox routing in VLSI design: Closing the complexity gap
• Detecting diamond necklaces in labeled dags
• Algebraic graph derivations for graphical calculi
• Definability equals recognizability of partial 3-trees
• One, two, three, many, or: Complexity aspects of dynamic network flows with dedicated arcs
• Approximate maxima finding of continuous functions under restricted budget (Extended abstract)
• The Optimal Cost Chromatic Partition problem for trees and interval graphs
• Modifying networks to obtain low cost trees
• On the hardness of allocating frequencies for hybrid networks
• Homogeneous sets and domination problems
• Independent spanning trees of product graphs
• Designing distrance-preserving fault-tolerant topologies
• Shortest path algorithms for nearly acyclic directed graphs
• Computing disjoint paths with length constraints
• Generalized edge-rankings of trees.