Algorithms and Computation 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006. Proceedings /
| Συγγραφή απο Οργανισμό/Αρχή: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Ηλεκτρονική πηγή Ηλ. βιβλίο |
| Γλώσσα: | English |
| Έκδοση: |
Berlin, Heidelberg :
Springer Berlin Heidelberg,
2006.
|
| Σειρά: | Lecture Notes in Computer Science,
4288 |
| Θέματα: | |
| Διαθέσιμο Online: | Full Text via HEAL-Link |
Πίνακας περιεχομένων:
- 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.
