ISAAC 2011: Accepted Papers

The 22nd International Symposium on Algorithms and Computation (ISAAC 2011) will be held in Yokohama, Japan, December 5-8, 2011.


Home | Call for papers | Accepted papers | Program | Best papers | Photos | Paper submission | Invited speakers | Events | Venue & Travel | Committees | Ad Com


Accepted Papers: ISAAC 2011

Ho-Lin Chen, David Doty and Shinnosuke Seki. Program Size and Temperature in Self-Assembly
Adrian Dumitrescu and Evan Hilscher. Animal Testing
Adrian Dumitrescu and Masud Hasan. Cutting out Polygons with a Circular Saw
Andreas Brandstädt and Raffaele Mosca. Dominating Induced Matchings for P7-Free Graphs in Linear Time
M. Reza Khani and Mohammad Salavatipour. Improved Approximations for Buy-at-bulk and Shallow-Light $k$-Steiner Trees and $(k,2)$-Subgraph
Rémy Belmonte, Petr Golovach, Pinar Heggernes, Pim van 't Hof, Marcin Kaminski and Daniel Paulusma. Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
Mark De Berg, Bettina Speckmann and Vincent Van Der Weele. Treemaps with Bounded Aspect Ratio
Yoshifumi Sakai. A new algorithm for the characteristic string problem under loose similarity criteria
Shota Yasutake, Kohei Hatano, Shuji Kijima, Eiji Takimoto and Masayuki Takeda. Online Linear Optimization over Permutations
Hiroshi Fujiwara, Takuma Kitano and Toshihiro Fujito. On the Best Possible Competitive Ratio for Multislope Ski Rental
Jakub Radoszewski and Wojciech Rytter. Hamiltonian paths in the square of a tree
Victor Campos, Sulamita Klein, Rudini Sampaio and Ana Silva. Two Fixed-Parameter algorithms for the cocoloring problem
Meng He, J. Ian Munro and Patrick K. Nicholson. Dynamic Range Majority Data Structures
Meng He, J. Ian Munro and Patrick K. Nicholson. Dynamic Range Selection in Linear Space
Joerg Laessig and Dirk Sudholt. Analysis of Speedups in Parallel Evolutionary Algorithms for Combinatorial Optimization
Amihood Amir, Estrella Eisenberg, Avivit Levy and Noa Lewenstein. Closest Periodic Vectors in Lp Spaces
Matias Korman. Minimizing interference in ad-hoc networks with bounded communication radius
Tomoyuki Yamakami. Optimization, Randomized Approximability, and  Boolean Constraint Satisfaction Problems
Markus Chimani and Matthias Woste. Contraction-based Steiner Tree Approximations in Practice
Sheng-Ying Hsiao. Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments
Dmitry Itsykson and Dmitry Sokolov. Lower bounds for myopic DPLL algorithms with a cut heuristic
Aviv Nisgav and Boaz Patt-Shamir. Improved Collaborative Filtering
Danny Z. Chen and Haitao Wang. Efficient Algorithms for the Weighted k-Center Problem on a Real Line
Kuan-Chieh Robert Tseng and David Kirkpatrick. Input-Thrifty Extrema Testing
Joseph A. Simons and Michael Goodrich. Fully Retroactive Approximate Range and Nearest Neighbor Searching
Kevin Verbeek, Kevin Buchin and Bettina Speckmann. Angle-Restricted Steiner Arborescences for Flow Map Layout
Sylvain Guillemot. Parameterized algorithms for inclusion of linear matchings
Cheng-Hsiao Tsou, Gen-Huey Chen and Ching-Chi Lin. Broadcasting in Heterogeneous Tree Networks with Uncertainty
Kai-Simon Goetzmann, Tobias Harks, Max Klimm and Konstantin Miller. Optimal File Distribution in Peer-to-Peer Networks
Luis Barba, Matias Korman, Stefan Langerman and Rodrigo Silveira. Computing the visibility polygon using few variables
Wei Yu and Guochuan Zhang. Improved Approximation Algorithms for Routing Shop Scheduling
Fabien De Montgolfier, Mauricio Soto and Laurent Viennot. Asymptotic Modularity of some Graph Classes
Mordecai Golin, John Iacono, Danny Krizanc, Rajeev Raman and Srinivasa Rao Satti. Encoding 2-D Range Maximum Queries
Gonzalo Navarro and Luis M. S. Russo. Space-Efficient Data-Analysis Queries on Grids
Danny Z. Chen and Haitao Wang. Outlier Respecting Points Approximation
Jeremy Hurwitz. A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers
Elaine Angelino, Michael Goodrich, Michael Mitzenmacher and Justin Thaler. External Memory Multimaps
Naoyuki Kamiyama. Robustness of Minimum Cost Arborescences
Mark De Berg, Atlas F. Cook Iv and Joachim Gudmundsson. Fast Fréchet Queries
Yun Cui, Jesper Jansson and Wing-Kin Sung. Algorithms for Building Consensus MUL-trees
Tobias Friedrich, Thomas Sauerwald and Alexandre Stauffer. Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions
Francis Chin, Henry C.M. Leung and S.M. Yiu. Adaptive Phenotype Testing for AND/OR Items
Hung-I Yu, Tien-Ching Lin and D. T. Lee. Finding Maximum Sum Segments in Sequences with Uncertainty
Taku Onodera and Tetsuo Shibuya. An Index Structure for Spaced Seed Search
Amihood Amir, Alberto Apostolico, Gad Landau, Avivit Levy, Moshe Lewenstein and Ely Porat. Range LCP
Ioannis Atsonios, Olivier Beaumont, Nicolas Hanusse and Yusik Kim. On Power-Law Distributed Balls in Bins and its Applications to View Size Estimation
Sepp Hartung, Rolf Niedermeier, Ondra Suchy and Jiong Guo. The Parameterized Complexity of Local Search for TSP, More Refined
Martin Dörnfelder, Jiong Guo, Christian Komusiewicz and Mathias Weller. On the Parameterized Complexity of Consensus Clustering
Michael Goodrich, Nodari Sitchinava and Qin Zhang. Sorting, Searching, and Simulation in the MapReduce Framework
Arash Farzan and Johannes Fischer. Compact Representation of Posets
Masatora Ogata, Yukiko Yamauchi, Shuji Kijima and Masafumi Yamashita. A Randomized Algorithm for Finding Frequent Elements in Streams Using O(log log N) Space
Naonori Kakimura, Kazuhisa Makino and Kento Seimi. Computing Knapsack Solutions with Cardinality Robustness
Muhammad Jawaherul Alam, Therese Biedl, Stefan Felsner, Andreas Gerasch, Michael Kaufmann and Stephen G. Kobourov. Linear-Time Algorithms for Proportional Contact Graph Representations
Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee, Jiangwei Pan, Hing-Fung Ting and Qin Zhang. Edit Distance to Monotonicity in Sliding Windows
Yakov Nekrich. External Memory Orthogonal Range Reporting with Fast Updates
Meng He, Ian Munro and Gelin Zhou. Path Queries in Weighted Trees
Chunhao Wang and Qian-Ping Gu. Computational Study on Bidimensionality Theory Based Algorithm for Longest Path Problem
Sarah Eisenstat, Erik D. Demaine, Martin L. Demaine, Tao B. Schardl, Jayson Lynch, Zachary Abel and Isaac Shapiro-Ellowitz. Folding Equilateral Plane Graphs
Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Lena Schlipf, Chan-Su Shin and Antoine Vigneron. Covering and Piercing Disks with Two Centers
Sharma V. Thankachan, Wing-Kai Hon, Rahul Shah and Chen-Hua Lu. Succinct Indexes for Circular Patterns
Danny Z. Chen and Haitao Wang. An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles
Yakov Nekrich. A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic  Query Time
Patrizio Angelini, Giuseppe Di Battista and Fabrizio Frati. Simultaneous Embedding of Embedded Planar Graphs
Huiwen Yu and Martin Fürer. Packing-Based Approximation Algorithm for the k-Set Cover Problem
Matt Gibson, Dongfeng Han, Milan Sonka and Xiaodong Wu. Maximum Weight Digital Regions Decomposable into Digital Star-Shaped Regions
Jochen Koenemann, Elyot Grant, Laura Sanitŕ and Adrian Bock. The School Bus Problem on Trees
Hee-Kap Ahn, Sang Won Bae, Christian Knauer, Mira Lee, Chan-Su Shin and Antoine Vigneron. Generating Realistic Roofs over a Rectilinear Polygon
Mong-Jen Kao and D.T. Lee. Capacitated Domination: Constant Factor Approximations for Planar Graphs
Lisa Hellerstein, Özgür Özkan and Linda Sellie. Max-Throughput for (Conservative) k-of-n Testing
Ryuta Ando and Tomomi Matsui. Algorithm for Single Allocation Problem on Hub-and-Spoke Networks in 2-Dimensional Plane
Cristina Bazgan, Morgan Chopin and Michael Fellows. Parameterized complexity of the firefighter problem
David Avis, Kazuo Iwama and Daichi Paku. Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs
Van Bang Le and Ragnar Nevries. Recognizing polar planar graphs using new results for monopolarity
Luca Castelli Aleardi and Olivier Devillers. Explicit array-based compact data structures for triangulations
Travis Gagie, Pawel Gawrychowski and Simon Puglisi. Faster Approximate Pattern Matching in Compressed Repetitive Texts
Pranabendu Misra, Ramanujan M. S., Venkatesh Raman and Saket Saurabh. A polynomial kernel for Feedback Arc Set  on Bipartite Tournaments