π/2-Angle Yao Graphs Are Spanners (English)
- New search for: Bose, P.
- New search for: Damian, M.
- New search for: Douieb, K.
- New search for: O Rourke, J.
- New search for: Seamone, B.
- New search for: Smid, M.
- New search for: Wuhrer, S.
- New search for: Bose, P.
- New search for: Damian, M.
- New search for: Douieb, K.
- New search for: O Rourke, J.
- New search for: Seamone, B.
- New search for: Smid, M.
- New search for: Wuhrer, S.
- New search for: Cheong, O.
- New search for: Chwa, K.-Y.
- New search for: Park, K.
In:
Algorithms and computation; ISAAC 2010
6507
;
446-457
;
2010
-
ISBN:
-
ISSN:
- Conference paper / Print
-
Title:π/2-Angle Yao Graphs Are Spanners
-
Contributors:Bose, P. ( author ) / Damian, M. ( author ) / Douieb, K. ( author ) / O Rourke, J. ( author ) / Seamone, B. ( author ) / Smid, M. ( author ) / Wuhrer, S. ( author ) / Cheong, O. / Chwa, K.-Y. / Park, K.
-
Conference:International Symposium; 21st, Algorithms and computation; ISAAC 2010 ; 2010 ; Jeju Island, Korea
-
Published in:Algorithms and computation; ISAAC 2010 , 6507 ; 446-457LECTURE NOTES IN COMPUTER SCIENCE , 6507 ; 446-457
-
Publisher:
- New search for: Springer
-
Place of publication:Berlin
-
Publication date:2010-01-01
-
Size:12 pages
-
Remarks:Includes bibliographical references and index
-
ISBN:
-
ISSN:
-
Type of media:Conference paper
-
Type of material:Print
-
Language:English
-
Keywords:
-
Source:
© Metadata Copyright the British Library Board and other contributors. All rights reserved.
Table of contents conference proceedings
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
D^2-Tree: A New Overlay with Deterministic BoundsBrodal, G.S. / Sioutas, S. / Tsichlas, K. / Zaroliagis, C. et al. | 2010
- 1
-
Regular Labelings and Geometric Structures (Abstract)Eppstein, D. et al. | 2010
- 2
-
Algorithmic Aspects of Secure Computation and Communication (Abstract)Franklin, M. et al. | 2010
- 3
-
Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness TournamentKarpinski, M. / Schudy, W. et al. | 2010
- 13
-
Efficient Indexes for the Positional Pattern Matching Problem and Two Related Problems over Small AlphabetsYu, C.-C. / Wang, B.-F. / Kuo, C.-C. et al. | 2010
- 15
-
A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2Berman, P. / Karpinski, M. / Zelikovsky, A. et al. | 2010
- 25
-
Dynamic Range Reporting in External MemoryNekrich, Y. et al. | 2010
- 25
-
Approximate PeriodicityAmir, A. / Eisenberg, E. / Levy, A. et al. | 2010
- 37
-
Approximating the Average Stretch Factor of Geometric GraphsCheng, S.-W. / Knauer, C. / Langerman, S. / Smid, M. et al. | 2010
- 37
-
A Cache-Oblivious Implicit Dictionary with the Working Set PropertyBrodal, G.S. / Kejlberg-Rasmussen, C. / Truelsen, J. et al. | 2010
- 49
-
The (p, q)-total Labeling Problem for TreesHasunuma, T. / Ishii, T. / Ono, H. / Uno, Y. et al. | 2010
- 49
-
Satisfiability with Index DependencyLiang, H. / He, J. et al. | 2010
- 61
-
Anonymous Fuzzy Identity-Based Encryption for Similarity SearchCheung, D.W. / Mamoulis, N. / Wong, W.K. / Yiu, S.M. / Zhang, Y. et al. | 2010
- 61
-
Drawing a Tree as a Minimum Spanning Tree ApproximationDi Giacomo, E. / Didimo, W. / Liotta, G. / Meijer, H. et al. | 2010
- 73
-
Improved Randomized Algorithms for 3-SATIwama, K. / Seto, K. / Takai, T. / Tamaki, S. et al. | 2010
- 73
-
k-Cyclic Orientations of GraphsKobayashi, Y. / Miyamoto, Y. / Tamaki, H. et al. | 2010
- 85
-
Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor SizeGu, Q.-P. / Tamaki, H. et al. | 2010
- 85
-
Quantum Counterfeit Coin ProblemsIwama, K. / Nishimura, H. / Raymond, R. / Teruyama, J. et al. | 2010
- 97
-
Maximum Overlap of Convex Polytopes under TranslationAhn, H.-K. / Cheng, S.-W. / Reinbacher, I. et al. | 2010
- 97
-
Priority Range TreesGoodrich, M.T. / Strash, D. et al. | 2010
- 109
-
Should Static Search Trees Ever Be Unbalanced?Bose, P. / Douieb, K. et al. | 2010
- 109
-
Approximate Shortest Homotopic Paths in Weighted RegionsCheng, S.-W. / Jin, J. / Vigneron, A. / Wang, Y. et al. | 2010
- 121
-
Spanning Ratio and Maximum Detour of Rectilinear Paths in the L~1 PlaneGrune, A. / Lin, T.-C. / Yu, T.-K. / Klein, R. / Langetepe, E. / Lee, D.T. / Poon, S.-H. et al. | 2010
- 121
-
Levelwise Mesh Sparsification for Shortest Path QueriesMiyamoto, Y. / Uno, T. / Kubo, M. et al. | 2010
- 132
-
Approximation and Hardness Results for the Maximum Edge q-Coloring ProblemAdamaszek, A. / Popa, A. et al. | 2010
- 133
-
Unit-Time Predecessor Queries on Massive Data SetsBrodnik, A. / Iacono, J. et al. | 2010
- 144
-
3-Colouring AT-Free Graphs in Polynomial TimeStacho, J. et al. | 2010
- 145
-
Popularity at Minimum CostKavitha, T. / Nasre, M. / Nimbhorkar, P. et al. | 2010
- 156
-
On Coloring Graphs without Induced ForestsBroersma, H. / Golovach, P.A. / Paulusma, D. / Song, J. et al. | 2010
- 157
-
Structural and Complexity Aspects of Line Systems of GraphsJirasek, J. / Klavik, P. et al. | 2010
- 168
-
On the Approximability of the Maximum Interval Constrained Coloring ProblemCanzar, S. / Elbassioni, K. / Elmasry, A. / Raman, R. et al. | 2010
- 169
-
Neighbor Systems, Jump Systems, and Bisubmodular PolyhedraShioura, A. et al. | 2010
- 180
-
Approximability of Constrained LCSJiang, M. et al. | 2010
- 182
-
Generating Trees on MultisetsZhuang, B. / Nagamochi, H. et al. | 2010
- 192
-
Approximation Algorithms for the Multi-Vehicle Scheduling ProblemBhattacharya, B. / Hu, Y. et al. | 2010
- 194
-
Seidel Minor, Permutation Graphs and Combinatorial PropertiesLimouzy, V. et al. | 2010
- 206
-
On Greedy Algorithms for Decision TreesCicalese, F. / Jacobs, T. / Laber, E. / Molinaro, M. et al. | 2010
- 206
-
Simultaneous Interval GraphsJampani, K.R. / Lubiw, A. et al. | 2010
- 218
-
Unbalanced Graph PartitioningLi, A. / Zhang, P. et al. | 2010
- 218
-
Single and Multiple Device DSA Problem, Complexities and Online AlgorithmsWu, W. / Tian, W. / Li, M. / Xue, C.J. / Chen, E. et al. | 2010
- 230
-
The Onion Diagram: A Voronoi-Like Tessellation of a Planar Line Space and Its Applications (Extended Abstract)Bae, S.W. / Shin, C.-S. et al. | 2010
- 230
-
On the Intersection of Tolerance and Cocomparability GraphsMertzios, G.B. / Zaks, S. et al. | 2010
- 241
-
Flows in One-Crossing-Minor-Free GraphsChambers, E. / Eppstein, D. et al. | 2010
- 242
-
Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin PackingZhang, Y. / Chen, J. / Chin, F.Y.L. / Han, X. / Ting, H.-F. / Tsin, Y.H. et al. | 2010
- 253
-
From Holant to #CSP and Back: Dichotomy for Holant^c ProblemsCai, J.-Y. / Huang, S. / Lu, P. et al. | 2010
- 254
-
On the Continuous CNN ProblemAugustine, J. / Gravin, N. et al. | 2010
- 266
-
Policies for Periodic Packet RoutingPeis, B. / Stiller, S. / Wiese, A. et al. | 2010
- 266
-
Computing Sparse Multiples of PolynomialsGiesbrecht, M. / Roche, D.S. / Tilak, H. et al. | 2010
- 279
-
Fractal Parallelism: Solving SAT in Bounded Space and TimeDuchier, D. / Durand-Lose, J. / Senot, M. et al. | 2010
- 279
-
Increasing Speed Scheduling and Flow SchedulingStiller, S. / Wiese, A. et al. | 2010
- 291
-
A Tighter Analysis of Work StealingTchiboukdjian, M. / Gast, N. / Trystram, D. / Roch, J.-L. / Bernard, J. et al. | 2010
- 291
-
Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time ComplexityFeree, H. / Hainry, E. / Hoyrup, M. / Pechoux, R. et al. | 2010
- 303
-
Approximating the Traveling Tournament Problem with Maximum Tour Length 2Thielen, C. / Westphal, S. et al. | 2010
- 304
-
New Upper Bounds on the Average PTF Density of Boolean FunctionsAmano, K. et al. | 2010
- 315
-
Alphabet Partitioning for Compressed Rank/Select and ApplicationsBarbay, J. / Gagie, T. / Navarro, G. / Nekrich, Y. et al. | 2010
- 316
-
An Optimal Algorithm for Computing Angle-Constrained SpannersCarmi, P. / Smid, M. et al. | 2010
- 327
-
Entropy-Bounded Representation of Point GridsFarzan, A. / Gagie, T. / Navarro, G. et al. | 2010
- 328
-
Approximating Minimum Bending Energy Path in a Simple CorridorXu, J. / Xu, L. / Xie, Y. et al. | 2010
- 339
-
Identifying Approximate Palindromes in Run-Length Encoded StringsChen, K.-Y. / Hsu, P.-H. / Chao, K.-M. et al. | 2010
- 340
-
Analysis of an Iterated Local Search Algorithm for Vertex ColoringSudholt, D. / Zarges, C. et al. | 2010
- 351
-
Minimum Cost Partitions of Trees with Supply and DemandIto, T. / Hara, T. / Zhou, X. / Nishizeki, T. et al. | 2010
- 353
-
Bounded Max-colorings of GraphsBampis, E. / Kononov, A. / Lucarelli, G. / Milis, I. et al. | 2010
- 363
-
Computing the (t, k)-Diagnosability of Component-Composition Graphs and Its ApplicationHsieh, S.-Y. / Chen, C.-A. et al. | 2010
- 366
-
Parameterized Algorithms for BoxicityAdiga, A. / Chitnis, R. / Saurabh, S. et al. | 2010
- 375
-
Why Depth-First Search Efficiently Identifies Two and Three-Connected GraphsElmasry, A. et al. | 2010
- 378
-
On Tractable Cases of Target Set SelectionNichterlein, A. / Niedermeier, R. / Uhlmann, J. / Weller, M. et al. | 2010
- 387
-
Beyond Good Shapes: Diffusion-Based Graph Partitioning is Relaxed Cut OptimizationMeyerhenke, H. et al. | 2010
- 390
-
Combining Two Worlds: Parameterised Approximation for Vertex CoverBrankovic, L. / Fernau, H. et al. | 2010
- 399
-
Induced Subgraph Isomorphism on Interval and Proper Interval GraphsHeggernes, P. / Meister, D. / Villanger, Y. et al. | 2010
- 403
-
Listing All Maximal Cliques in Sparse Graphs in Near-Optimal TimeEppstein, D. / Loffler, M. / Strash, D. et al. | 2010
- 410
-
Testing Simultaneous Planarity When the Common Graph Is 2-ConnectedHaeupler, B. / Jampani, K.R. / Lubiw, A. et al. | 2010
- 415
-
Lower Bounds for Howard's Algorithm for Finding Minimum Mean-Cost CyclesHansen, T.D. / Zwick, U. et al. | 2010
- 422
-
Computing the Discrete Frechet Distance with Imprecise InputAhn, H.-K. / Knauer, C. / Scherfenberg, M. / Schlipf, L. / Vigneron, A. et al. | 2010
- 427
-
Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-CutBomze, I. / Chimani, M. / Junger, M. / Ljubic, I. / Mutzel, P. / Zey, B. et al. | 2010
- 434
-
Connectivity Graphs of Uncertainty RegionsChambers, E. / Erickson, A. / Fekete, S. / Lenchner, J. / Sember, J. / Venkatesh, S. / Stege, U. / Stolpner, S. / Weibel, C. / Whitesides, S. et al. | 2010
- 440
-
An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related ProblemsSpoerhase, J. et al. | 2010
- 446
-
π/2-Angle Yao Graphs Are SpannersBose, P. / Damian, M. / Douieb, K. / O Rourke, J. / Seamone, B. / Smid, M. / Wuhrer, S. et al. | 2010
- 451
-
A Faster Algorithm for the Maximum Even Factor ProblemBabenko, M.A. et al. | 2010
- 458
-
Identifying Shapes Using Self-assembly (Extended Abstract)Patitz, M.J. / Summers, S.M. et al. | 2010