22. ISAAC 2011: Yokohama, Japan

Invited Talk I

• Dorothea Wagner:
  Algorithm Engineering for Route Planning - An Update -. 1-5
  

Invited Talk II

• Sanjeev Arora:
  Semidefinite Programming and Approximation Algorithms: A Survey. 6-9
  

Approximation Algorithms I

• Adrian Bock, Elyot Grant, Jochen Könemann, Laura Sanità:
  The School Bus Problem on Trees. 10-19
  
• M. Reza Khani, Mohammad R. Salavatipour:
  Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k, 2)-Subgraph. 20-29
  
• Wei Yu, Guochuan Zhang:
  Improved Approximation Algorithms for Routing Shop Scheduling. 30-39
  
• Markus Chimani, Matthias Woste:
  Contraction-Based Steiner Tree Approximations in Practice. 40-49
  

Computational Geometry I

• Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Lena Schlipf, Chan-Su Shin, Antoine Vigneron:
  Covering and Piercing Disks with Two Centers. 50-59
  
• Hee-Kap Ahn, Sang Won Bae, Christian Knauer, Mira Lee, Chan-Su Shin, Antoine Vigneron:
  Generating Realistic Roofs over a Rectilinear Polygon. 60-69
  
• Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira:
  Computing the Visibility Polygon Using Few Variables. 70-79
  
• Matias Korman:
  Minimizing Interference in Ad-Hoc Networks with Bounded Communication Radius. 80-89
  

Graph Algorithms

• Jakub Radoszewski, Wojciech Rytter:
  Hamiltonian Paths in the Square of a Tree. 90-99
  
• Andreas Brandstädt, Raffaele Mosca:
  Dominating Induced Matchings for P 7-free Graphs in Linear Time. 100-109
  
• Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Marcin Kaminski, Daniël Paulusma:
  Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths. 110-119
  
• Van Bang Le, Ragnar Nevries:
  Recognizing Polar Planar Graphs Using New Results for Monopolarity. 120-129
  
• Naoyuki Kamiyama:
  Robustness of Minimum Cost Arborescences. 130-139
  

Data Structures I

• Meng He, J. Ian Munro, Gelin Zhou:
  Path Queries in Weighted Trees. 140-149
  
• Amr Elmasry, Meng He, J. Ian Munro, Patrick K. Nicholson:
  Dynamic Range Majority Data Structures. 150-159
  
• Meng He, J. Ian Munro, Patrick K. Nicholson:
  Dynamic Range Selection in Linear Space. 160-169
  
• Yakov Nekrich:
  A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time. 170-179
  
• Mordecai J. Golin, John Iacono, Danny Krizanc, Rajeev Raman, S. Srinivasa Rao:
  Encoding 2D Range Maximum Queries. 180-189
  

Distributed Systems

• Tobias Friedrich, Thomas Sauerwald, Alexandre Stauffer:
  Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions. 190-199
  
• Cheng-Hsiao Tsou, Gen-Huey Chen, Ching-Chi Lin:
  Broadcasting in Heterogeneous Tree Networks with Uncertainty. 200-209
  
• Kai-Simon Goetzmann, Tobias Harks, Max Klimm, Konstantin Miller:
  Optimal File Distribution in Peer-to-Peer Networks. 210-219
  

Computational Geometry II

• Adrian Dumitrescu, Evan Hilscher:
  Animal Testing. 220-229
  
• Adrian Dumitrescu, Masud Hasan:
  Cutting Out Polygons with a Circular Saw. 230-239
  
• Mark de Berg, Atlas F. Cook IV, Joachim Gudmundsson:
  Fast Fréchet Queries. 240-249
  

Graph Drawing and Information Visualization

• Kevin Buchin, Bettina Speckmann, Kevin Verbeek:
  Angle-Restricted Steiner Arborescences for Flow Map Layout. 250-259
  
• Mark de Berg, Bettina Speckmann, Vincent van der Weele:
  Treemaps with Bounded Aspect Ratio. 260-270
  
• Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati:
  Simultaneous Embedding of Embedded Planar Graphs. 271-280
  
• Muhammad Jawaherul Alam, Therese C. Biedl, Stefan Felsner, Andreas Gerasch, Michael Kaufmann, Stephen G. Kobourov:
  Linear-Time Algorithms for Hole-Free Rectilinear Proportional Contact Graph Representations. 281-291
  

Data Structures II

• Michael T. Goodrich, Joseph A. Simons:
  Fully Retroactive Approximate Range and Nearest Neighbor Searching. 292-301
  
• Arash Farzan, Johannes Fischer:
  Compact Representation of Posets. 302-311
  
• Luca Castelli Aleardi, Olivier Devillers:
  Explicit Array-Based Compact Data Structures for Triangulations. 312-322
  
• Gonzalo Navarro, Luís M. S. Russo:
  Space-Efficient Data-Analysis Queries on Grids. 323-332
  

Parameterized Algorithms I

• Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh:
  A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments. 333-343
  
• Sheng-Ying Hsiao:
  Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments. 344-353
  
• Sylvain Guillemot:
  Parameterized Algorithms for Inclusion of Linear Matchings. 354-363
  
• Chunhao Wang, Qian-Ping Gu:
  Computational Study on Bidimensionality Theory Based Algorithm for Longest Path Problem. 364-373
  

Parallel and External Memory Algorithms

• Michael T. Goodrich, Nodari Sitchinava, Qin Zhang:
  Sorting, Searching, and Simulation in the MapReduce Framework. 374-383
  
• Elaine Angelino, Michael T. Goodrich, Michael Mitzenmacher, Justin Thaler:
  External-Memory Multimaps. 384-394
  
• Yakov Nekrich:
  External Memory Orthogonal Range Reporting with Fast Updates. 395-404
  
• Jörg Lässig, Dirk Sudholt:
  Analysis of Speedups in Parallel Evolutionary Algorithms for Combinatorial Optimization - (Extended Abstract). 405-414
  

Game Theory and Internet Algorithms

• David Avis, Kazuo Iwama, Daichi Paku:
  Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs. 415-424
  
• Aviv Nisgav, Boaz Patt-Shamir:
  Improved Collaborative Filtering. 425-434
  
• Fabien de Montgolfier, Mauricio Soto, Laurent Viennot:
  Asymptotic Modularity of Some Graph Classes. 435-444
  

Computational Complexity

• Ho-Lin Chen, David Doty, Shinnosuke Seki:
  Program Size and Temperature in Self-Assembly. 445-453
  
• Tomoyuki Yamakami:
  Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems. 454-463
  
• Dmitry Itsykson, Dmitry Sokolov:
  Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic. 464-473
  

Approximation Algorithms II

• Ryuta Ando, Tomomi Matsui:
  Algorithm for Single Allocation Problem on Hub-and-Spoke Networks in 2-Dimensional Plane. 474-483
  
• Martin Fürer, Huiwen Yu:
  Packing-Based Approximation Algorithm for the k-Set Cover Problem. 484-493
  
• Mong-Jen Kao, D. T. Lee:
  Capacitated Domination: Constant Factor Approximations for Planar Graphs. 494-503
  

Randomized Algorithms

• Ioannis Atsonios, Olivier Beaumont, Nicolas Hanusse, Yusik Kim:
  On Power-Law Distributed Balls in Bins and Its Applications to View Size Estimation. 504-513
  
• Masatora Ogata, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita:
  A Randomized Algorithm for Finding Frequent Elements in Streams Using O(loglogN) Space. 514-523
  
• Jeremy Hurwitz:
  A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers - (Extended Abstract). 524-533
  

Online and Streaming Algorithms

• Shota Yasutake, Kohei Hatano, Shuji Kijima, Eiji Takimoto, Masayuki Takeda:
  Online Linear Optimization over Permutations. 534-543
  
• Hiroshi Fujiwara, Takuma Kitano, Toshihiro Fujito:
  On the Best Possible Competitive Ratio for Multislope Ski Rental. 544-553
  
• Kuan-Chieh Robert Tseng, David G. Kirkpatrick:
  Input-Thrifty Extrema Testing. 554-563
  
• Ho-Leung Chan, Tak Wah Lam, Lap-Kei Lee, Jiangwei Pan, Hing-Fung Ting, Qin Zhang:
  Edit Distance to Monotonicity in Sliding Windows. 564-573
  

Computational Geometry III

• Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl, Isaac Shapiro-Ellowitz:
  Folding Equilateral Plane Graphs. 574-583
  
• Danny Z. Chen, Haitao Wang:
  Efficient Algorithms for the Weighted k-Center Problem on a Real Line. 584-593
  
• Danny Z. Chen, Haitao Wang:
  Outlier Respecting Points Approximation. 594-603
  
• Danny Z. Chen, Haitao Wang:
  An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles. 604-613
  

Parameterized Algorithms II

• Jiong Guo, Sepp Hartung, Rolf Niedermeier, Ondrej Suchý:
  The Parameterized Complexity of Local Search for TSP, More Refined. 614-623
  
• Martin Dörnfelder, Jiong Guo, Christian Komusiewicz, Mathias Weller:
  On the Parameterized Complexity of Consensus Clustering. 624-633
  
• Victor Campos, Sulamita Klein, Rudini Menezes Sampaio, Ana Silva:
  Two Fixed-Parameter Algorithms for the Cocoloring Problem. 634-642
  
• Cristina Bazgan, Morgan Chopin, Michael R. Fellows:
  Parameterized Complexity of the Firefighter Problem. 643-652
  

String Algorithms

• Travis Gagie, Pawel Gawrychowski, Simon J. Puglisi:
  Faster Approximate Pattern Matching in Compressed Repetitive Texts. 653-662
  
• Yoshifumi Sakai:
  A New Algorithm for the Characteristic String Problem under Loose Similarity Criteria. 663-672
  
• Wing-Kai Hon, Chen-Hua Lu, Rahul Shah, Sharma V. Thankachan:
  Succinct Indexes for Circular Patterns. 673-682
  
• Amihood Amir, Alberto Apostolico, Gad M. Landau, Avivit Levy, Moshe Lewenstein, Ely Porat:
  Range LCP. 683-692
  

Optimization

• Naonori Kakimura, Kazuhisa Makino, Kento Seimi:
  Computing Knapsack Solutions with Cardinality Robustness. 693-702
  
• Lisa Hellerstein, Özgür Özkan, Linda Sellie:
  Max-Throughput for (Conservative) k-of-n Testing. 703-713
  
• Amihood Amir, Estrella Eisenberg, Avivit Levy, Noa Lewenstein:
  Closest Periodic Vectors in L p Spaces. 714-723
  
• Matt Gibson, Dongfeng Han, Milan Sonka, Xiaodong Wu:
  Maximum Weight Digital Regions Decomposable into Digital Star-Shaped Regions. 724-733
  

Computational Biology

• Hung-I Yu, Tien-Ching Lin, D. T. Lee:
  Finding Maximum Sum Segments in Sequences with Uncertainty. 734-743
  
• Yun Cui, Jesper Jansson, Wing-Kin Sung:
  Algorithms for Building Consensus MUL-trees. 744-753
  
• Francis Y. L. Chin, Henry C. M. Leung, Siu Ming Yiu:
  Adaptive Phenotype Testing for AND/OR Items. 754-763
  
• Taku Onodera, Tetsuo Shibuya:
  An Index Structure for Spaced Seed Search. 764-772
  

Last update Fri May 25 08:23:37 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page