21. ISAAC 2010: Jeju Island, Korea

Data Structure and Algorithm II

• Gerth Stølting Brodal, Spyros Sioutas, Kostas Tsichlas, Christos D. Zaroliagis:
  D²-Tree: A New Overlay with Deterministic Bounds. 1-12
  
• Chih-Chiang Yu, Biing-Feng Wang, Chung-Chin Kuo:
  Efficient Indexes for the Positional Pattern Matching Problem and Two Related Problems over Small Alphabets. 13-24
  
• Yakov Nekrich:
  Dynamic Range Reporting in External Memory. 25-36
  
• Gerth Stølting Brodal, Casper Kejlberg-Rasmussen, Jakob Truelsen:
  A Cache-Oblivious Implicit Dictionary with the Working Set Property. 37-48
  

Graph Algorithm II

• Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno:
  The (p, q)-total Labeling Problem for Trees. 49-60
  
• Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer:
  Drawing a Tree as a Minimum Spanning Tree Approximation. 61-72
  
• Yasuaki Kobayashi, Yuichiro Miyamoto, Hisao Tamaki:
  k-cyclic Orientations of Graphs. 73-84
  
• Qian-Ping Gu, Hisao Tamaki:
  Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size. 85-96
  

Computational Geometry II

• Hee-Kap Ahn, Siu-Wing Cheng, Iris Reinbacher:
  Maximum Overlap of Convex Polytopes under Translation. 97-108
  
• Siu-Wing Cheng, Jiongxin Jin, Antoine Vigneron, Yajun Wang:
  Approximate Shortest Homotopic Paths in Weighted Regions. 109-120
  
• Ansgar Grüne, Tien-Ching Lin, Teng-Kai Yu, Rolf Klein, Elmar Langetepe, D. T. Lee, Sheung-Hung Poon:
  Spanning Ratio and Maximum Detour of Rectilinear Paths in the L₁ Plane. 121-131
  

Graph Coloring II

• Anna Adamaszek, Alexandru Popa:
  Approximation and Hardness Results for the Maximum Edge q-coloring Problem. 132-143
  
• Juraj Stacho:
  3-Colouring AT-Free Graphs in Polynomial Time. 144-155
  
• Hajo Broersma, Petr A. Golovach, Daniël Paulusma, Jian Song:
  On Coloring Graphs without Induced Forests. 156-167
  

Approximation Algorithm II

• Stefan Canzar, Khaled M. Elbassioni, Amr Elmasry, Rajiv Raman:
  On the Approximability of the Maximum Interval Constrained Coloring Problem. 168-179
  
• Minghui Jiang:
  Approximability of Constrained LCS. 180-191
  
• Binay K. Bhattacharya, Yuzhuang Hu:
  Approximation Algorithms for the Multi-Vehicle Scheduling Problem. 192-205
  
• Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, Marco Molinaro:
  On Greedy Algorithms for Decision Trees. 206-217
  

Online Algorithm

• Weiwei Wu, Wanyong Tian, Minming Li, Chun Jason Xue, Enhong Chen:
  Single and Multiple Device DSA Problem, Complexities and Online Algorithms. 218-229
  
• Sang Won Bae, Chan-Su Shin:
  The Onion Diagram: A Voronoi-Like Tessellation of a Planar Line Space and Its Applications - (Extended Abstract). 230-241
  
• Yong Zhang, Jing-Chi Chen, Francis Y. L. Chin, Xin Han, Hing-Fung Ting, Yung H. Tsin:
  Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing. 242-253
  
• John Augustine, Nick Gravin:
  On the Continuous CNN Problem. 254-265
  

Scheduling

• Britta Peis, Sebastian Stiller, Andreas Wiese:
  Policies for Periodic Packet Routing. 266-278
  
• Sebastian Stiller, Andreas Wiese:
  Increasing Speed Scheduling and Flow Scheduling. 279-290
  
• Marc Tchiboukdjian, Nicolas Gast, Denis Trystram, Jean-Louis Roch, Julien Bernard:
  A Tighter Analysis of Work Stealing. 291-302
  
• Clemens Thielen, Stephan Westphal:
  Approximating the Traveling Tournament Problem with Maximum Tour Length 2. 303-314
  

Data Structure and Algorithm III

• Jérémy Barbay, Travis Gagie, Gonzalo Navarro, Yakov Nekrich:
  Alphabet Partitioning for Compressed Rank/Select and Applications. 315-326
  
• Arash Farzan, Travis Gagie, Gonzalo Navarro:
  Entropy-Bounded Representation of Point Grids. 327-338
  
• Kuan-Yu Chen, Ping-Hui Hsu, Kun-Mao Chao:
  Identifying Approximate Palindromes in Run-Length Encoded Strings. 339-350
  

Graph Algorithm III

• Takehiro Ito, Takuya Hara, Xiao Zhou, Takao Nishizeki:
  Minimum Cost Partitions of Trees with Supply and Demand. 351-362
  
• Sun-Yuan Hsieh, Chun-An Chen:
  Computing the (t, k)-Diagnosability of Component-Composition Graphs and Its Application. 363-374
  
• Amr Elmasry:
  Why Depth-First Search Efficiently Identifies Two and Three-Connected Graphs. 375-386
  
• Henning Meyerhenke:
  Beyond Good Shapes: Diffusion-Based Graph Partitioning Is Relaxed Cut Optimization. 387-398
  
• Pinar Heggernes, Daniel Meister, Yngve Villanger:
  Induced Subgraph Isomorphism on Interval and Proper Interval Graphs. 399-409
  

Computational Geometry III

• Bernhard Haeupler, Krishnam Raju Jampani, Anna Lubiw:
  Testing Simultaneous Planarity When the Common Graph Is 2-Connected. 410-421
  
• Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, Antoine Vigneron:
  Computing the Discrete Fréchet Distance with Imprecise Input. 422-433
  
• Erin W. Chambers, Alejandro Erickson, Sándor P. Fekete, Jonathan Lenchner, Jeff Sember, Venkatesh Srinivasan, Ulrike Stege, Svetlana Stolpner, Christophe Weibel, Sue Whitesides:
  Connectivity Graphs of Uncertainty Regions. 434-445
  
• Prosenjit Bose, Mirela Damian, Karim Douïeb, Joseph O'Rourke, Ben Seamone, Michiel H. M. Smid, Stefanie Wuhrer:
  pi/2-Angle Yao Graphs Are Spanners. 446-457
  
• Matthew J. Patitz, Scott M. Summers:
  Identifying Shapes Using Self-assembly - (Extended Abstract). 458-469
  

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