05693nam 22007455 450 99646626100331620200630021211.03-540-48385-310.1007/3-540-57899-4(CKB)1000000000234099(SSID)ssj0000323614(PQKBManifestationID)11247884(PQKBTitleCode)TC0000323614(PQKBWorkID)10300455(PQKB)10957344(DE-He213)978-3-540-48385-4(PPN)155193481(EXLCZ)99100000000023409920121227d1994 u| 0engurnn|008mamaatxtccrGraph-Theoretic Concepts in Computer Science[electronic resource] 19th International Workshop, WG '93, Utrecht, The Netherlands, June 16 - 18, 1993. Proceedings /edited by Jan van Leeuwen1st ed. 1994.Berlin, Heidelberg :Springer Berlin Heidelberg :Imprint: Springer,1994.1 online resource (XI, 437 p.) Lecture Notes in Computer Science,0302-9743 ;790Bibliographic Level Mode of Issuance: Monograph3-540-57899-4 Near-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 -- A rainbow about T-colorings for complete graphs -- Approximating the chromatic polynomial of a graph -- Asteroidal triple-free graphs -- The parallel complexity of elimination ordering procedures -- Dually chordal graphs -- The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions -- Regular marked Petri nets -- The asynchronous committee meeting problem -- Gossiping in vertex-disjoint paths mode in interconnection networks -- The folded Petersen network: A 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 -- Two algorithms for finding rectangular duals of planar graphs -- A more compact visibility representation.This 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.Lecture Notes in Computer Science,0302-9743 ;790ComputersDiscrete mathematicsApplication softwareAlgorithmsCombinatoricsComputer logicTheory of Computationhttps://scigraph.springernature.com/ontologies/product-market-codes/I16005Discrete Mathematicshttps://scigraph.springernature.com/ontologies/product-market-codes/M29000Computer Applicationshttps://scigraph.springernature.com/ontologies/product-market-codes/I23001Algorithm Analysis and Problem Complexityhttps://scigraph.springernature.com/ontologies/product-market-codes/I16021Combinatoricshttps://scigraph.springernature.com/ontologies/product-market-codes/M29010Logics and Meanings of Programshttps://scigraph.springernature.com/ontologies/product-market-codes/I1603XComputers.Discrete mathematics.Application software.Algorithms.Combinatorics.Computer logic.Theory of Computation.Discrete Mathematics.Computer Applications.Algorithm Analysis and Problem Complexity.Combinatorics.Logics and Meanings of Programs.004/.01/5115Leeuwen Jan vanedthttp://id.loc.gov/vocabulary/relators/edtInternational Workshop on Graph-Theoretic Concepts in Computer Science(19th :1993 :Utrecht, Netherlands)BOOK996466261003316Graph-Theoretic Concepts in Computer Science772292UNISA