03388nmm a2200361 u 4500001001200000003002700012005001700039007002400056008004100080020001800121100001700139245019100156260006300347300003100410505099100441505048701432505011001919653002102029653002202050653001702072653001802089653002102107653004602128653001802174653003602192710003402228041001902262989003802281490003802319856007002357082001002427520058902437EB000658550EBX0100000000000000051163200000000000000.0cr|||||||||||||||||||||140122 ||| eng a97835404838541 aLeeuwen, Jan00aGraph-Theoretic Concepts in Computer SciencehElektronische Ressourceb19th International Workshop, WG '93 Utrecht, The Netherlands, June 16–18, 1993 Proceedingscedited by Jan Leeuwen aBerlin, HeidelbergbSpringer Berlin Heidelbergc1994, 1994 aXI, 437 pbonline resource0 aNear-optimal dominating sets in dense random graphs in polynomial expected time -- Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality -- Hierarchically specified unit disk graphs -- Bounded tree-width and LOGCFL -- On reduction algorithms for graphs with small treewidth -- Algorithms and complexity of sandwich problems in graphs (extended abstract) -- On-line graph algorithms for incremental compilation -- Average case analysis of fully dynamic connectivity for directed graphs -- Fully dynamic maintenance of vertex cover -- Dynamic algorithms for graphs with treewidth 2 -- Short disjoint cycles in graphs with degree constraints -- Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs -- Towards a solution of the Holyer's problem -- Graphs, hypergraphs and hashing -- Coloring k-colorable graphs in constant expected parallel time -- Deciding 3-colourability in less than O(1.415n) steps -- 0 aA new versatile multiprocessor interconnection topology -- Fast load balancing in Cayley graphs and in circuits -- Concurrent flows and packet routing in Cayley graphs (Preliminary version) -- On multi-label linear interval routing schemes -- An ‘All pairs shortest paths’ distributed algorithm using 2n 2 messages -- Linear layouts of generalized hypercubes -- Graph ear decompositions and graph embeddings -- Improved bounds for the crossing numbers on surfaces of genus g -- 0 aTwo algorithms for finding rectangular duals of planar graphs -- A more compact visibility representation aComputer science aComputer software aLogic design aCombinatorics aComputer Science aAlgorithm Analysis and Problem Complexity aCombinatorics aLogics and Meanings of Programs2 aSpringerLink (Online service)07aeng2ISO 639-2 bSBAaSpringer Book Archives -20040 aLecture Notes in Computer Science uhttp://dx.doi.org/10.1007/3-540-57899-4?nosfx=yxVerlag3Volltext0 a005.1 aThis volume contains the proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG '93, held near Utrecht, The Netherlands, in 1993. The papers are grouped into parts on: hard problems on classes of graphs, structural graph theory, dynamic graph algorithms, structure-oriented graph algorithms, graph coloring, AT-free and chordal graphs, circuits and nets, graphs and interconnection networks, routing and shortest paths, and graph embedding and layout. The 35 revised papers were chosen from 92 submissions after a careful refereeing process