000 04571nam a22005655i 4500
001 978-3-540-68529-6
003 DE-He213
005 20160624102050.0
007 cr nn 008mamaa
008 121227s1996 gw | s |||| 0|eng d
020 _a9783540685296
_9978-3-540-68529-6
024 7 _a10.1007/3-540-61422-2
_2doi
050 4 _aQA76.9.A43
072 7 _aUMB
_2bicssc
072 7 _aCOM051300
_2bisacsh
082 0 4 _a005.1
_223
245 1 0 _aAlgorithm Theory — SWAT'96
_h[electronic resource] :
_b5th Scandinavian Workshop on Algorithm Theory Reykjavík, Iceland, July 3–5, 1996 Proceedings /
_cedited by Rolf Karlsson, Andrzej Lingas.
260 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c1996.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c1996.
300 _aX, 462 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aLecture Notes in Computer Science,
_x0302-9743 ;
_v1097
505 0 _aDerandomization via small sample spaces -- The randomized complexity of maintaining the minimum -- Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning -- Service-constrained network design problems -- Approximate hypergraph coloring -- Facility dispersion and remote subgraphs -- The constrained minimum spanning tree problem -- Randomized approximation of the constraint satisfaction problem -- On the hardness of global and local approximation -- Approximation algorithms for the maximum satisfiability problem -- On the hardness of approximating the minimum consistent OBDD problem -- Computing the unrooted maximum agreement subtree in sub-quadratic time -- Greedily finding a dense subgraph -- Using sparsification for parametric minimum spanning tree problems -- Vertex partitioning problems on partial k-trees -- Making an arbitrary filled graph minimal by removing fill edges -- Sorting and searching revisted -- Lower bounds for dynamic transitive closure, planar point location, and parentheses matching -- Optimal pointer algorithms for finding nearest common ancestors in dynamic trees -- Neighborhood graphs and distributed ?+1-coloring -- Communication complexity of gossiping by packets -- Optimal cost-sensitive distributed minimum spanning tree algorithm -- A linear time algorithm for the feasibility of pebble motion on trees -- Linear-time heuristics for minimum weight rectangulation -- Visibility with multiple reflections -- A fast heuristic for approximating the minimum weight triangulation -- Neighbours on a grid -- On two dimensional packing -- Optimal orthogonal drawings of triconnected plane graphs -- Walking streets faster -- Safe and efficient traffic laws for mobile robots -- Progress in selection -- Probabilistic ancestral sequences and multiple alignments -- Efficient algorithms for Lempel-Ziv encoding -- The deterministic complexity of parallel multisearch -- Priority queues on parallel machines -- Binary search trees: How low can you go? -- Boolean analysis of incomplete examples.
520 _aThis book constitutes the refereed proceedings of the Fifth Scandinavian Workshop on Algorithm Theory, SWAT '96, held in Reykjavik, Iceland, in July 1996. The 35 full papers included in the book in revised version were carefully selected from a total of 95 submissions; also included are abstracts or full versions of three invited talks by prominent researchers. All in all, the collection of articles reports state-of-the-art results on various topics of current design and analysis of algorithms.
650 0 _aComputer science.
650 0 _aData structures (Computer science).
650 0 _aComputer software.
650 0 _aComputer graphics.
650 0 _aCombinatorics.
650 1 4 _aComputer Science.
650 2 4 _aAlgorithm Analysis and Problem Complexity.
650 2 4 _aComputation by Abstract Devices.
650 2 4 _aData Structures.
650 2 4 _aData Storage Representation.
650 2 4 _aComputer Graphics.
650 2 4 _aCombinatorics.
700 1 _aKarlsson, Rolf.
_eeditor.
700 1 _aLingas, Andrzej.
_eeditor.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9783540614227
786 _dSpringer
830 0 _aLecture Notes in Computer Science,
_x0302-9743 ;
_v1097
856 4 0 _uhttp://dx.doi.org/10.1007/3-540-61422-2
942 _2EBK7024
_cEBK
999 _c36318
_d36318