Algorithms and Computation [[electronic resource] ] : 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings / / edited by Tetsuo Asano

• Record Nr.: UNISA996466065303316
• Pubbl/distr/stampa: Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006
• ISBN: 3-540-49696-3
• Edizione: [1st ed. 2006.]
• Descrizione fisica: 1 online resource (XX, 766 p.)
• Collana: Theoretical Computer Science and General Issues, , 2512-2029 ; ; 4288
• Disciplina: 005.1
• Soggetti: Computer programming; Algorithms; Computer science—Mathematics; Discrete mathematics; Numerical analysis; Computer networks; Computer graphics; Programming Techniques; Discrete Mathematics in Computer Science; Numerical Analysis; Computer Communication Networks; Computer Graphics
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di bibliografia: Includes bibliographical references and author index.
• Nota di contenuto: Invited Talks -- Stable Matching Problems -- Delaunay Meshing of Surfaces -- Best Paper 2006 -- Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction -- Best Student Paper 2006 -- Branching and Treewidth Based Exact Algorithms -- Session 1A: Algorithms and Data Structures -- Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees -- Optimal Algorithms for Tower of Hanoi Problems with Relaxed Placement Rules -- Flexible Word Design and Graph Labeling -- Session 1B: Online Algorithms -- Frequency Allocation Problems for Linear Cellular ; Networks -- Finite-State Online Algorithms and Their Automated Competitive Analysis -- Offline Sorting Buffers on Line -- Session 2A: Approximation Algorithms -- Approximating Tree Edit Distance Through String Edit Distance -- A 6-Approximation Algorithm for Computing Smallest Common AoN-Supertree with Application to the Reconstruction of Glycan Trees -- Improved Approximation for Single-Sink Buy-at-Bulk -- Approximability of Partitioning Graphs with Supply and Demand -- Session 2B: Graphs -- Convex Grid Drawings of Plane Graphs with Rectangular Contours -- Algorithms on Graphs with Small Dominating Targets -- Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems -- On Estimating Path Aggregates over Streaming Graphs -- Session 3A: Computational Geometry -- Diamond Triangulations Contain Spanners of Bounded Degree -- Optimal Construction of the City Voronoi Diagram -- Relations Between Two Common Types of Rectangular Tilings -- Quality Tetrahedral Mesh Generation for Macromolecules -- On Approximating the TSP with Intersecting Neighborhoods -- Session 3B: Computational Complexity -- Negation-Limited Complexity of Parity and Inverters -- The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem -- Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete -- Parameterized Problems on Coincidence Graphs -- On 2-Query Codeword Testing with Near-Perfect Completeness -- Session 4A: Algorithms and Data Structures -- Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance -- Efficient Algorithms for the Optimal-Ratio Region Detection Problems in Discrete Geometry with Applications -- On Locating Disjoint Segments with Maximum Sum of Densities -- Two-Tier Relaxed Heaps -- Session 4B: Games and Networks -- The Interval Liar Game -- How Much Independent Should Individual Contacts Be to Form a Small–World? -- Faster Centralized Communication in Radio Networks -- On the Runtime and Robustness of Randomized Broadcasting -- Session 5A: Combinatorial Optimization and Computational Biology -- Local Search in Evolutionary Algorithms: The Impact of the Local Search Frequency -- Non-cooperative Facility Location and Covering Games -- Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees -- Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications -- Algorithms for Computing Variants of the Longest Common Subsequence Problem -- Session 5B: Graphs -- Constructing Labeling Schemes Through Universal Matrices -- Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions -- Analyzing Disturbed Diffusion on Networks -- Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs -- On Isomorphism and Canonization of Tournaments and Hypertournaments -- Session 6A: Algorithms and Data Structures -- Efficient Algorithms for the Sum Selection Problem and K Maximum Sums Problem -- Deterministic Random Walks on the Two-Dimensional Grid -- Improving Time and Space Complexity for Compressed Pattern Matching -- Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems -- Session 6B: Graphs -- A Simple Message Passing Algorithm for Graph Partitioning Problems -- Minimal Interval Completion Through Graph Exploration -- Balanced Cut Approximation in Random Geometric Graphs -- Improved Algorithms for the Minmax-Regret 1-Center Problem -- Session 7A: Approximation Algorithms -- On Approximating the Maximum Simple Sharing Problem -- Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures -- Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering ; Problems -- Session 7B: Graphs -- Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii -- Efficient Prüfer-Like Coding and Counting Labelled Hypertrees -- Intuitive Algorithms and t-Vertex Cover -- Session 8A: Combinatorial Optimization and Quantum Computing -- Politician’s Firefighting -- Runtime Analysis of a Simple Ant Colony Optimization Algorithm -- Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems -- Resources Required for Preparing Graph States -- Session 8B: Online Algorithms -- Online Multi-path Routing in a Maze -- On the On-Line k-Truck Problem with Benefit Maximization -- Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels -- Online Packet Admission and Oblivious Routing in Sensor Networks -- Session 9A: Computational Geometry -- Field Splitting Problems in Intensity-Modulated Radiation Therapy -- Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy -- A New Approximation Algorithm for Multidimensional Rectangle Tiling -- Tessellation of Quadratic Elements -- Session 9B: Distributed Computing and Cryptography -- Effective Elections for Anonymous Mobile Agents -- Gathering Asynchronous Oblivious Mobile Robots in a Ring -- Provably Secure Steganography and the Complexity of Sampling.