Algorithms -- ESA 2004 : 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings / / edited by Susanne Albers, Tomasz Radzik

• Pubblicazione: Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2004
• Edizione: 1st ed. 2004.
• Descrizione fisica: 1 online resource (XXXVI, 836 p.)
• Disciplina: 005.1
• Soggetto topico: Software engineering; Algorithms; Numerical analysis; Computer science—Mathematics; Data structures (Computer science); Computer networks; Software Engineering/Programming and Operating Systems; Algorithm Analysis and Problem Complexity; Numeric Computing; Discrete Mathematics in Computer Science; Data Structures; Computer Communication Networks
• Persona (resp. second.): AlbersSusanne; RadzikTomasz
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di bibliografia: Includes bibliographical references at the end of each chapters and index.
• Nota di contenuto: Invited Lectures -- A Survey of FPT Algorithm Design Techniques with an Emphasis on Recent Advances and Connections to Practical Computing -- Algorithmic Aspects of Web Search Engines -- Design and Analysis Track -- Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects -- Swap and Mismatch Edit Distance -- Path Decomposition Under a New Cost Measure with Applications to Optical Network Design -- Optimal External Memory Planar Point Enclosure -- Maximizing Throughput in Multi-queue Switches -- An Improved Algorithm for CIOQ Switches -- Labeling Smart Dust -- Graph Decomposition Lemmas and Their Role in Metric Embedding Methods -- Modeling Locality: A Probabilistic Analysis of LRU and FWF -- An Algorithm for Computing DNA Walks -- Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems -- Direct Routing: Algorithms and Complexity -- Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families -- A Parameterized Algorithm for Upward Planarity Testing -- Fisher Equilibrium Price with a Class of Concave Utility Functions -- Hardness and Approximation Results for Packing Steiner Trees -- Approximation Hardness of Dominating Set Problems -- Improved Online Algorithms for Buffer Management in QoS Switches -- Time Dependent Multi Scheduling of Multicast -- Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems -- The Average Case Analysis of Partition Sorts -- A Fast Distributed Algorithm for Approximating the Maximum Matching -- Extreme Points Under Random Noise -- Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings -- On Variable-Sized Multidimensional Packing -- An Inductive Construction for Plane Laman Graphs via Vertex Splitting -- Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems -- On the Evolution of Selfish Routing -- Competitive Online Approximation of the Optimal Search Ratio -- Incremental Algorithms for Facility Location and k-Median -- Dynamic Shannon Coding -- Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries -- Negotiation-Range Mechanisms: Coalition-Resistant Markets -- Approximation Algorithms for Quickest Spanning Tree Problems -- An Approximation Algorithm for Maximum Triangle Packing -- Approximate Parameterized Matching -- Approximation of Rectangle Stabbing and Interval Stabbing Problems -- Fast 3-Coloring Triangle-Free Planar Graphs -- Approximate Unions of Lines and Minkowski Sums -- Radio Network Clustering from Scratch -- Seeking a Vertex of the Planar Matching Polytope in NC -- Equivalence of Search Capability Among Mobile Guards with Various Visibilities -- Load Balancing in Hypercubic Distributed Hash Tables with Heterogeneous Processors -- On the Stability of Multiple Partner Stable Marriages with Ties -- Flows on Few Paths: Algorithms and Lower Bounds -- Maximum Matchings in Planar Graphs via Gaussian Elimination -- Fast Multipoint Evaluation of Bivariate Polynomials -- On Adaptive Integer Sorting -- Tiling a Polygon with Two Kinds of Rectangles -- On Dynamic Shortest Paths Problems -- Uniform Algorithms for Deterministic Construction of Efficient Dictionaries -- Fast Sparse Matrix Multiplication -- Engineering and Applications Track -- An Experimental Study of Random Knapsack Problems -- Contraction and Treewidth Lower Bounds -- Load Balancing of Indivisible Unit Size Tokens in Dynamic and Heterogeneous Networks -- Comparing Real Algebraic Numbers of Small Degree -- Code Flexibility and Program Efficiency by Genericity: Improving Cgal ’s Arrangements -- Finding Dominators in Practice -- Data Migration on Parallel Disks -- Classroom Examples of Robustness Problems in Geometric Computations -- Stable Minimum Storage Merging by Symmetric Comparisons -- On Rectangular Cartograms -- Multi-word Atomic Read/Write Registers on Multiprocessor Systems -- Beyond Optimal Play in Two-Person-Zerosum Games -- Solving Geometric Covering Problems by Data Reduction -- Efficient IP Table Lookup via Adaptive Stratified Trees with Selective Reconstructions -- Super Scalar Sample Sort -- Construction of Minimum-Weight Spanners -- A Straight Skeleton Approximating the Medial Axis -- Non-additive Shortest Paths.
• Sommario/riassunto: This volume contains the 70 contributed papers and abstracts of two invited l- tures presented at the 12th Annual European Symposium on Algorithms (ESA 2004), held in Bergen, Norway, September 14-17, 2004. The papers in each s- tion of the proceedings are arranged alphabetically. The three distinguished - vited speakers were David Eppstein, Michael Fellows and Monika Henzinger. As in the last two years, ESA had two tracks, with separate program c- mittees, which dealt respectively with: - the design and mathematical analysis of algorithms (the "Design and A- lysis" track); - real-world applications, engineering and experimental analysis of algorithms (the "Engineering and Applications" track). Previous ESAs were held at Bad Honnef, Germany (1993); Utrecht, The Netherlands (1994); Corfu, Greece (1995); Barcelona, Spain (1996); Graz, A- tria (1997); Venice, Italy (1998); Prague, Czech Republic (1999); Saarbruc ¨ ken, ? Germany (2000); Arhus, Denmark (2001); Rome, Italy (2002); and Budapest, Hungary (2003). The predecessor to the Engineering and Applications track of ESA was the annual Workshop on Algorithm Engineering (WAE). Previous WAEs were held in Venice, Italy (1997); Saarbruc ¨ ken, Germany (1998); London, ? UK (1999); Saarbruc ¨ ken, Germany (2000); and Arhus, Denmark (2001). The proceedings of the previous ESAs were published as Springer-Verlag's LNCS volumes 726, 855, 979, 1284, 1461, 1643, 1879, 2161, 2461, and 2832. The proceedingsoftheWAEsfrom1999onwardswerepublishedasSpringer-Verlag's LNCS volumes 1668, 1982, and 2141.
• Titolo autorizzato: Algorithms -- ESA 2004
• ISBN: 3-540-30140-2
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910767564503321
• Lo trovi qui: Univ. Federico II
• Serie: Lecture Notes in Computer Science, . 0302-9743 ; ; 3221