LEADER 13312nam 22009375 450 001 996466265103316 005 20230223093640.0 010 $a3-642-25591-4 024 7 $a10.1007/978-3-642-25591-5 035 $a(CKB)3390000000021461 035 $a(SSID)ssj0000609137 035 $a(PQKBManifestationID)11411935 035 $a(PQKBTitleCode)TC0000609137 035 $a(PQKBWorkID)10610421 035 $a(PQKB)10713476 035 $a(DE-He213)978-3-642-25591-5 035 $a(MiAaPQ)EBC6302270 035 $a(MiAaPQ)EBC5585174 035 $a(Au-PeEL)EBL5585174 035 $a(OCoLC)768204302 035 $a(PPN)157506576 035 $a(EXLCZ)993390000000021461 100 $a20111201d2011 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aAlgorithms and Computation$b[electronic resource] $e22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings /$fedited by Takao Asano, Shin-ichi Nakano, Yoshio Okamoto, Osamu Watanabe 205 $a1st ed. 2011. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2011. 215 $a1 online resource (XVIII, 775 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v7074 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-642-25590-6 327 $aIntro -- Title page -- Preface -- Organization -- Table of Contents -- Invited Talk I -- Algorithm Engineering for Route Planning- An Update - -- References -- Invited Talk II -- Semidefinite Programming and Approximation Algorithms: A Survey -- References -- Approximation Algorithms I -- The School Bus Problem on Trees -- Introduction -- Our Results -- Related Work -- Preliminaries -- A 4-Approximation to the SBP on Trees -- A 12.5-Approximation to the Uncapacitated SBP-R on Trees -- References -- Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k, 2)-Subgraph -- Introduction -- Shallow-Light Steiner Trees -- An O(logn)-Approximation for the (k, 2)-Subgraph Problem -- References -- Improved Approximation Algorithms for Routing Shop Scheduling -- Introduction -- Previous Work -- Our Results and Techniques -- Preliminaries -- Routing Open Shop -- Routing Flow Shop -- References -- Contraction-Based Steiner Tree Approximations in Practice -- Introduction -- History -- Contraction Framework -- Algorithm Engineering -- Experiments -- Conclusions and Thoughts -- References -- Computational Geometry I -- Covering and Piercing Disks with Two Centers -- Introduction -- Intersecting Disks with Two Centers -- Decision Algorithm -- Optimization Algorithm -- Covering Disks with Two Centers -- The General Case -- The Restricted Case -- References -- Generating Realistic Roofs over a Rectilinear Polygon -- Introduction -- Preliminaries -- Properties of Realistic Roofs -- Local Properties of Valleys and Ridges -- Global Structure of Realistic Roofs -- Enumerating Realistic Roofs and Computing Optimal Roofs -- References -- Computing the Visibility Polygon Using Few Variables -- Introduction -- Preliminaries -- An O(n) Algorithm Using O(1) Variables -- An O(n logr) Algorithm Using O(logr) Variables -- Closing Remarks. 327 $aReferences -- Minimizing Interference in Ad-Hoc Networks with Bounded Communication Radius -- Introduction -- Definitions and Results -- Layered Nearest Neighbor Algorithm -- Bounded Radius Network -- Conclusion -- References -- Graph Algorithms -- Hamiltonian Paths in the Square of a Tree -- Introduction -- Caterpillars and Horsetails -- 2H-Paths in (u,v)-Horsetails -- Efficient Algorithm for Horstail Queries -- References -- Dominating Induced Matchings for P7-free Graphs in Linear Time -- Introduction and Basic Notions -- Simple Properties of Graphs with Dominating Induced Matching -- Structure of P7-free Graphs with Dominating Induced Matching -- Distance Levels with Respect to an M-Edge in a P3 -- Edges in and between Ti and Tj, i =j -- The Algorithm for the General P7-free Case -- Conclusion -- References -- Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths -- Introduction -- Preliminaries -- Set-Restricted Disjoint Paths -- Contractions and Induced Minors in Chordal Graphs -- Concluding Remarks -- References -- Recognizing Polar Planar Graphs Using New Results for Monopolarity -- Introduction -- Hardness Results -- A 2-SAT Approach and a Superclass of Chair-Free Graphs -- A Superclass of Hole-Free Graphs -- Some Efficiently Solvable Cases of Polarity for Planar Graphs -- Conclusion -- References -- Robustness of Minimum Cost Arborescences -- Introduction -- Fulkerson's Algorithm -- A Sufficient Condition is Necessary -- A Necessary Condition is Sufficient -- References -- Data Structures I -- Path Queries in Weighted Trees -- Introduction -- Previous Work -- Our Results -- Properties of Ordinal Trees -- A Pointer Machine Data Structure -- Optimizations in the RAM model -- Linear Space, but Slower Reporting -- Slightly More Space, Much Faster Reporting -- References -- Dynamic Range Majority Data Structures. 327 $aIntroduction -- Previous Work -- Our Results -- Dynamic Data Structures in One Dimension -- Supporting Queries -- Supporting Updates -- Speedup for Integer Coordinates -- Dynamic Data Structures in Higher Dimensions -- References -- Dynamic Range Selection in Linear Space -- Introduction -- Previous Work -- Our Results -- Linear Space Data Structure -- Space Efficient Ranking Trees -- Answering Queries -- Handling Updates -- Dynamic Arrays -- Concluding Remarks -- References -- A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time -- Introduction -- A Data Structure with Optimal Query Time -- Compact Representation -- References -- Encoding 2D Range Maximum Queries -- Introduction -- Random Input -- Small m -- Data Structures for 2D-RMQ -- Conclusions and Open Problems -- References -- Distributed Systems -- Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions -- Introduction -- Precise Model and Results -- The Diameter of the Largest Connected Component -- References -- Broadcasting in Heterogeneous Tree Networks with Uncertainty -- Introduction -- Preliminaries -- Finding a Minmax-Regret Broadcast Center -- Correctness -- Time Complexity -- Conclusion -- References -- Optimal File Distribution in Peer-to-Peer Networks -- Introduction -- Homogeneous Symmetric Capacities -- Heterogeneous Symmetric Capacities -- References -- Computational Geometry II -- Animal Testing -- Introduction -- Algorithm 1 Based on Fundamental Polygonsand Davenport-Schinzel Sequences -- Algorithm 2 Based on Euler-Poincare? Formula -- References -- Cutting Out Polygons with a Circular Saw -- Introduction -- Preliminaries -- Algorithm -- References -- Fast Fre?chet Queries -- Introduction -- Preliminaries -- The Data Structure -- Making Part of the Query -- Relative Error -- References -- Graph Drawing and Information Visualization. 327 $aAngle-Restricted Steiner Arborescences for Flow Map Layout -- Introduction -- Optimal Flux Trees -- Spiral Trees -- Computing Spiral Trees -- Approximating Spiral Trees in the Presenceof Obstacles -- Rectilinear Steiner Arborescences -- Spiral Trees -- References -- Treemaps with Bounded Aspect Ratio -- Introduction -- Convex Treemaps -- Ortho-Convex Treemaps -- Conclusions -- References -- Simultaneous Embedding of Embedded Planar Graphs -- Introduction and Overview -- Preliminaries -- Computing a Sefe-Fe of Three Embedded Planar Graphs -- Sefe-Fe and Sge-Fe of k Embedded Graphs Is NP-Hard -- References -- Linear-Time Algorithms for Hole-Free Rectilinear Proportional Contact Graph Representations -- Introduction -- Representations for Maximal Planar Graphs -- Representations of Planar 3-trees -- Representations for Maximal Outer-Planar Graphs -- Conclusion -- References -- Data Structures II -- Fully Retroactive Approximate Range and Nearest Neighbor Searching -- Introduction -- Related Work -- Our Results -- A General Approach to Retroactivity -- Main Results -- References -- Compact Representation of Posets -- Introduction -- Our Work in Context -- Contributions -- Preliminaries -- Posets -- Transitive Reductions -- Succinct Data Structures -- The Representation -- Storing the Chains -- Storing the Order Relation between Chains -- Operations -- Operation reachability(x,y) -- Operations succG(x) and predG(x) -- Operation range(x,y) -- Operation adjGr(x,y) -- Operations succGr(x) and predGr(x) -- Operations a-succGr(x) and a-predGr(x) -- Operations LUB(x1, ..., xt) and GLB(x1, ..., xt) -- Operations a-LUB(x1, ..., xt) and a-GLB(x1, ..., xt) -- Summary and Open Questions -- References -- Explicit Array-Based Compact Data Structures for Triangulations -- Introduction -- Existing Mesh Data Structures -- Preliminaries -- Compactly Representing Triangulations. 327 $aThe First Data Structure: Simple and Still Redundant -- More Compact Solutions, via Minimal Schnyder Woods -- Further Reducing the Space Requirement -- Experimental Results -- References -- Space-Efficient Data-Analysis Queries on Grids -- Introduction -- Wavelet Trees -- Representation of Grids -- Dynamism -- Statistical Queries -- Range Sum, Average, and Variance -- Range Minima and Maxima -- Range Median and Quantiles -- Range Majority -- Range Successor and Predecessor -- Dynamism -- Final Remarks -- References -- Parameterized Algorithms I -- A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments -- Introduction -- Preliminaries -- Modular Partitions -- Reductions and Kernel -- Data Reduction Rules -- Analysis of Kernel Size -- Conclusion -- References -- Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments -- Introduction -- Preliminaries -- Canonical Sequence for Acyclic Bipartite Tournament -- Allying Sequence of Node Sets and Increasing Subsequence of Node Sets -- Consistent Node Sequence and Compatible Node Sequence -- A Reduction -- Framework of Our Proof for the Main Lemma -- Good Sequence -- Framework for Proving the Main Lemma -- Dynamic Programming for Proving Lemma 4 -- References -- Parameterized Algorithms for Inclusion of Linear Matchings -- Introduction -- Problem Definition -- Algorithms for Linear Matching Inclusion -- An FPT Algorithm for Parameters d and k -- An FPT Algorithm for Parameter p -- An Algorithm for Nesting-Free Patterns -- Hardness Results -- Hardness of Linear Matching Inclusion -- Hardness of Nesting-Free 2-Interval Pattern -- References -- Computational Study on Bidimensionality Theory Based Algorithm for Longest Path Problem -- Introduction -- Preliminaries -- Algorithms Implemented -- Computational Results -- Results for Longest Paths -- Results for Grid/Cylinder Minors. 327 $aConcluding Remarks. 330 $aThis book constitutes the refereed proceedings of the 22nd International Symposium on Algorithms and Computation, ISAAC 2011, held in Yokohama, Japan in December 2011. The 76 revised full papers presented together with two invited talks were carefully reviewed and selected from 187 submissions for inclusion in the book. This volume contains topics such as approximation algorithms; computational geometry; computational biology; computational complexity; data structures; distributed systems; graph algorithms; graph drawing and information visualization; optimization; online and streaming algorithms; parallel and external memory algorithms; parameterized algorithms; game theory and internet algorithms; randomized algorithms; and string algorithms. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v7074 606 $aAlgorithms 606 $aComputer science?Mathematics 606 $aDiscrete mathematics 606 $aComputer networks 606 $aComputer graphics 606 $aArtificial intelligence?Data processing 606 $aNumerical analysis 606 $aAlgorithms 606 $aDiscrete Mathematics in Computer Science 606 $aComputer Communication Networks 606 $aComputer Graphics 606 $aData Science 606 $aNumerical Analysis 615 0$aAlgorithms. 615 0$aComputer science?Mathematics. 615 0$aDiscrete mathematics. 615 0$aComputer networks. 615 0$aComputer graphics. 615 0$aArtificial intelligence?Data processing. 615 0$aNumerical analysis. 615 14$aAlgorithms. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aComputer Communication Networks. 615 24$aComputer Graphics. 615 24$aData Science. 615 24$aNumerical Analysis. 676 $a005.1 702 $aAsano$b Takao$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aNakano$b Shin-ichi$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aOkamoto$b Yoshio$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aWatanabe$b Osamu$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996466265103316 996 $aAlgorithms and Computation$9771857 997 $aUNISA