000 10728nam a22006135i 4500
001 978-3-642-10631-6
003 DE-He213
005 20240730184106.0
007 cr nn 008mamaa
008 100301s2009 gw | s |||| 0|eng d
020 _a9783642106316
_9978-3-642-10631-6
024 7 _a10.1007/978-3-642-10631-6
_2doi
050 4 _aQ336
072 7 _aUN
_2bicssc
072 7 _aCOM021000
_2bisacsh
072 7 _aUN
_2thema
082 0 4 _a005.7
_223
245 1 0 _aAlgorithms and Computation
_h[electronic resource] :
_b20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings /
_cedited by Ying Fei Dong, Ding-Zhu Du, Oscar H. Ibarra.
250 _a1st ed. 2009.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2009.
300 _aXXIX, 1228 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v5878
505 0 _aBubblesort and Juggling Sequences -- A Proof of the Molecular Conjecture -- Exact Algorithms for Dominating Clique Problems -- Enumerating Stereoisomers of Tree Structured Molecules Using Dynamic Programming -- Exact Algorithms for the Bottleneck Steiner Tree Problem -- Exact Algorithms for Set Multicover and Multiset Multicover Problems -- Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm -- Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems -- On Protein Structure Alignment under Distance Constraint -- A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability -- Max-Coloring Paths: Tight Bounds and Extensions -- Fréchet Distance Problems in Weighted Regions -- The Complexity of Solving Stochastic Games on Graphs -- Computational Complexity of Cast Puzzles -- New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body -- Reconstructing Numbers from Pairwise Function Values -- Hilbert's Thirteenth Problem and Circuit Complexity -- Interval Stabbing Problems in Small Integer Ranges -- Online Sorted Range Reporting -- Data Structures for Approximate Orthogonal Range Counting -- Dynamic 3-Sided Planar Range Queries with Expected Doubly Logarithmic Time -- Untangled Monotonic Chains and Adaptive Range Search -- Geodesic Spanners on Polyhedral Surfaces -- Approximating Points by a Piecewise Linear Function: I -- Approximating Points by a Piecewise Linear Function: II. Dealing with Outliers -- Computing the Map of Geometric Minimal Cuts -- On the Camera Placement Problem -- Graph Orientations with Set Connectivity Requirements -- A Linear Vertex Kernel for Maximum Internal Spanning Tree -- Geometric Minimum Diameter Minimum Cost Spanning Tree Problem -- On Shortest Disjoint Paths in PlanarGraphs -- An Optimal Labeling for Node Connectivity -- SOFA: Strategyproof Online Frequency Allocation for Multihop Wireless Networks -- 1-Bounded Space Algorithms for 2-Dimensional Bin Packing -- On the Advice Complexity of Online Problems -- Online Knapsack Problems with Limited Cuts -- Online Paging for Flash Memory Devices -- Shifting Strategy for Geometric Graphs without Geometry -- Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics -- Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time -- Minimum Covering with Travel Cost -- Route-Enabling Graph Orientation Problems -- Complexity of Approximating the Vertex Centroid of a Polyhedron -- Popular Matchings with Variable Job Capacities -- On the Tightness of the Buhrman-Cleve-Wigderson Simulation -- Bounds on Contention Management Algorithms -- Algorithmic Folding Complexity -- Min-Energy Scheduling for Aligned Jobs in Accelerate Model -- Posi-modular Systems with Modulotone Requirements under Permutation Constraints -- Generalized Reduction to Compute Toric Ideals -- Linear and Sublinear Time Algorithms for Basis of Abelian Groups -- Good Programming in Transactional Memory -- Induced Packing of Odd Cycles in a Planar Graph -- On the Infinitesimal Rigidity of Bar-and-Slider Frameworks -- Exploration of Periodically Varying Graphs -- Parameterized Complexity of Arc-Weighted Directed Steiner Problems -- Worst Case Analysis for Pickup and Delivery Problems with Consecutive Pickups and Deliveries -- Minimum Cycle Bases of Weighted Outerplanar Graphs -- Bandwidth on AT-Free Graphs -- Editing Graphs into Disjoint Unions of Dense Clusters -- A Certifying Algorithm for 3-Colorability of P 5-Free Graphs -- Parameterizing Cut Sets in a Graph by the Number of Their Components -- Inapproximability of Maximal Strip Recovery -- The Complexity of Perfect Matching Problems on Dense Hypergraphs -- On Lower Bounds for Constant Width Arithmetic Circuits -- Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria -- The Identity Correspondence Problem and Its Applications -- Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs -- An Improved Approximation Algorithm for the Traveling Tournament Problem -- The Fault-Tolerant Facility Allocation Problem -- Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks -- Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms -- The Directed Hausdorff Distance between Imprecise Point Sets -- Computing Multidimensional Persistence -- Locating an Obnoxious Line among Planar Objects -- Finding Fullerene Patches in Polynomial Time -- Convex Drawings of Internally Triconnected Plane Graphs on O(n 2) Grids -- A Self-stabilizing and Local Delaunay Graph Construction -- Succinct Greedy Geometric Routing in the Euclidean Plane -- Electric Routing and Concurrent Flow Cutting -- A Polynomial-Time Algorithm for the Universally Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths -- Strong Robustness of Randomized Rumor Spreading Protocols -- Data Structures for Range Median Queries -- Deletion without Rebalancing in Multiway Search Trees -- Counting in the Presence of Memory Faults -- A Simple, Fast, and Compact Static Dictionary -- Reconstructing Polygons from Scanner Data -- Computing Large Matchings in Planar Graphs with Fixed Minimum Degree -- Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs -- Covering a Graph with a Constrained Forest (Extended Abstract) -- Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs -- Upward Star-Shaped Polyhedral Graphs -- Conditional Hardness of Approximating Satisfiable Max 3CSP-q -- The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract) -- Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement -- Step-Assembly with a Constant Number of Tile Types -- Lower Bounds on Fast Searching -- Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity -- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1?+?? ) Time -- PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k -- Optimal Randomized Algorithm for the Density Selection Problem -- New Results on Simple Stochastic Games -- Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences -- Succinct Index for Dynamic Dictionary Matching -- Range Non-overlapping Indexing -- Querying Two Boundary Points for Shortest Paths in a Polygonal Domain -- Pattern Matching for 321-Avoiding Permutations -- Folding a Better Checkerboard -- Finding All Approximate Gapped Palindromes -- General Pseudo-random Generators from Weaker Models of Computation -- Random Generation and Enumeration of Bipartite Permutation Graphs -- A Combinatorial Algorithm for Horn Programs -- Online Maximum Directed Cut -- Maintaining Nets and Net Trees under Incremental Motion -- Distributed Scheduling of Parallel Hybrid Computations -- I/O-Efficient Contour Tree Simplification -- Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes -- I/O and Space-Efficient Path Traversal in Planar Graphs -- Improved Algorithms for Finding Consistent Superstrings Based on aNew Graph Model -- Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint (Extended Abstract) -- Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets -- On Partitioning a Graph into Two Connected Subgraphs.
520 _aThis book constitutes the refereed proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC 2009, held in Honolulu, Hawaii, USA in December 2009. The 120 revised full papers presented were carefully reviewed and selected from 279 submissions for inclusion in the book. This volume contains topics such as algorithms and data structures, approximation algorithms, combinatorial optimization, computational biology, computational complexity, computational geometry, cryptography, experimental algorithm methodologies, graph drawing and graph algorithms, internet algorithms, online algorithms, parallel and distributed algorithms, quantum computing and randomized algorithms.
650 0 _aArtificial intelligence
_xData processing.
_921787
650 0 _aComputer science
_xMathematics.
_93866
650 0 _aMathematics
_xData processing.
_919904
650 0 _aAlgorithms.
_93390
650 0 _aDiscrete mathematics.
_912873
650 1 4 _aData Science.
_934092
650 2 4 _aMathematics of Computing.
_931875
650 2 4 _aComputational Mathematics and Numerical Analysis.
_931598
650 2 4 _aAlgorithms.
_93390
650 2 4 _aDiscrete Mathematics in Computer Science.
_931837
700 1 _aDong, Ying Fei.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9134508
700 1 _aDu, Ding-Zhu.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9134509
700 1 _aIbarra, Oscar H.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9134510
710 2 _aSpringerLink (Online service)
_9134511
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783642106309
776 0 8 _iPrinted edition:
_z9783642106323
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v5878
_9134512
856 4 0 _uhttps://doi.org/10.1007/978-3-642-10631-6
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cELN
999 _c92186
_d92186