LEADER 06491nam 22007455 450 001 996465749103316 005 20200701173609.0 010 $a3-540-47766-7 024 7 $a10.1007/BFb0015401 035 $a(CKB)1000000000234366 035 $a(SSID)ssj0000321213 035 $a(PQKBManifestationID)11247376 035 $a(PQKBTitleCode)TC0000321213 035 $a(PQKBWorkID)10263056 035 $a(PQKB)10357815 035 $a(DE-He213)978-3-540-47766-2 035 $a(PPN)155167294 035 $a(EXLCZ)991000000000234366 100 $a20121227d1995 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithms and Computations$b[electronic resource] $e6th International Symposium, ISAAC '95 Cairns, Australia, December 4 - 6, 1995. Proceedings Proceedings. /$fedited by John Staples, Peter Eades, Naoki Katoh, Alistair Moffat 205 $a1st ed. 1995. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d1995. 215 $a1 online resource (XVIII, 450 p.) 225 1 $aLecture Notes in Computer Science,$x0302-9743 ;$v1004 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-60573-8 327 $aAlgorithmic problems arising from Genome informatics -- An approximation algorithm for alphabet indexing problem -- A fast and space-economical algorithm for length-limited coding -- Computing in linear time a chord from which a simple polygon is weakly internally visible -- Competitive searching in polygons?Beyond generalised streets -- Finding a shortest pair of paths on the plane with obstacles and crossing areas -- Logspace verifiers, NC, and NP -- Structure in average case complexity -- Some geometric lower bounds -- The I/O-complexity of Ordered Binary-Decision Diagram manipulation -- Two arc disjoint paths in Eulerian digraphs -- Finding dense subgraphs -- Finding smallest supertrees -- Weighted domination on cocomparability graphs -- The parallel complexity of approximating the High Degree Subgraph problem -- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs -- Greedy approximations of independent sets in low degree graphs -- Practical logic -- An approximation algorithm for MAX 3-SAT -- Learning of restricted RNLC graph languages -- Optimal information delivery -- On the complexity of testing for catastrophic faults -- Scheduling parallel tasks with individual deadlines -- Orders of Gauss periods in finite fields -- A hard problem that is almost always easy -- Computing the Tutte polynomial of a graph of moderate size -- More efficient parallel flow algorithms -- Linear-time in-place selection in less than 3n comparisons -- Heap construction: Optimal in both worst and average cases? -- Fast approximate dictionary matching -- Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation (extended abstract) -- Searching for a monotone function by independent threshold queries -- A fast and simple algorithm for identifying 2-monotonic positive Boolean functions -- Deciding bisimulation and trace equivalences for systems with many identical processes -- Should Amdahl's Law be repealed? -- Embeddings of hyper-rings in hypercubes -- A fast algorithm for computing optimal rectilinear Steiner trees for extremal point sets -- Algorithms for finding f-colorings of partial k-trees -- Spanning closed trail and hamiltonian cycle in grid graphs -- A linear time algorithm for finding maximal planar subgraphs -- Illumination with orthogonal floodlights -- No quadrangulation is extremely odd -- Finding the medial axis of a simple polygon in linear time -- The first subquadratic algorithm for complete linkage clustering -- Matching nuts and bolts faster -- Linear matching-time algorithm for the directed graph isomorphism problem -- A resource assignment problem on graphs -- NC algorithms for partitioning sparse graphs into induced forests with an application. 330 $aThis book presents the refereed proceedings of the 6th International Symposium on Algorithms and Computation, ISAAC '95, held in Cairns, Australia, in December 1995. The 45 revised full papers presented together with the abstracts of three invited talks were selected from a total of 130 submissions. The papers address many current aspects of research and advanced applications of algorithms and computations; among the topics covered are graph theory and graph algorithms, computational geometry, computational logics, searching and sorting, approximation and optimization, algebraic manipulation, and coding. 410 0$aLecture Notes in Computer Science,$x0302-9743 ;$v1004 606 $aComputers 606 $aAlgorithms 606 $aCombinatorics 606 $aProbabilities 606 $aStatistics  606 $aTheory of Computation$3https://scigraph.springernature.com/ontologies/product-market-codes/I16005 606 $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021 606 $aComputation by Abstract Devices$3https://scigraph.springernature.com/ontologies/product-market-codes/I16013 606 $aCombinatorics$3https://scigraph.springernature.com/ontologies/product-market-codes/M29010 606 $aProbability Theory and Stochastic Processes$3https://scigraph.springernature.com/ontologies/product-market-codes/M27004 606 $aStatistics, general$3https://scigraph.springernature.com/ontologies/product-market-codes/S0000X 615 0$aComputers. 615 0$aAlgorithms. 615 0$aCombinatorics. 615 0$aProbabilities. 615 0$aStatistics . 615 14$aTheory of Computation. 615 24$aAlgorithm Analysis and Problem Complexity. 615 24$aComputation by Abstract Devices. 615 24$aCombinatorics. 615 24$aProbability Theory and Stochastic Processes. 615 24$aStatistics, general. 676 $a004.0151 702 $aStaples$b John$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aEades$b Peter$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aKatoh$b Naoki$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aMoffat$b Alistair$4edt$4http://id.loc.gov/vocabulary/relators/edt 906 $aBOOK 912 $a996465749103316 996 $aAlgorithms and computations$92240113 997 $aUNISA