InhaltsangabeOn improved time bounds for permutation graph problems.- A simple test for interval graphs.- Tolerance graphs and orders.- On scheduling problems restricted to interval orders.- Scheduling with incompatible jobs.- Generalized coloring for tree-like graphs.- Optimal (parallel) algorithms for the all-to-all vertices distance problem for certain graph classes.- Topology of parallel networks and computational complexity (extended abstract).- Parallel triangulation of nonconvex polytopes.- Kayles on special classes of graphs - An application of Sprague-Grundy theory.- A linear time algorithm for isomorphism of graphs of bounded average genus.- Improved algorithms for routing on two-dimensional grids.- Minimum rectilinear steiner trees for intervals on two parallel lines.- A new characterization of tree medians with applications to distributed algorithms.- The 3-edge-components and a structural description of all 3-edge-cuts in a graph.- On assembly of four-connected graphs.- On the homogeneous decomposition of graphs.- Embeddings in recursive combinatorial networks.- On shortcutting digraphs.- An efficient algorithm to recognize prime undirected graphs.- On the complexity of partial order properties.- Probabilistic graph grammars.- Single vs. double pushout derivations of graphs.- Hexagonal grid drawings.- Graph algorithms = iteration + data structures?.- Petri nets, hypergraphs and conflicts (preliminary version).- Analysis and manipulation of Boolean functions in terms of decision graphs.- The expressiveness of silence: Tight bounds for synchronous communication of information using bits and silence.- The power and the limitations of local computations on graphs.

Hersteller:
Springer Verlag GmbH
juergen.hartmann@springer.com
Tiergartenstr. 17
DE 69121 Heidelberg