Detailansicht
Graph-Theoretic Concepts in Computer Science
18th International Workshop, WG '92, Wiesbaden-Naurod, Germany, June 18-20,1992.Proceedings, Lecture Notes in Computer Science 657
ISBN/EAN: 9783540564027
Umbreit-Nr.: 1431938
Sprache:
Englisch
Umfang: ix, 355 S.
Format in cm:
Einband:
kartoniertes Buch
Erschienen am 26.02.1993
- Zusatztext
- 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.