Otfried Cheong

Algorithms and Computation: Proceedings - Lecture Notes in Computer Science / Theoretical Computer Science and General Issues Otfried Cheong

Marc Notes: International conference proceedings.; Includes bibliographical references.; Avail. in electronic form. Table of Contents: Invited Talks -- Regular Labelings and Geometric Structures (Abstract) / David Eppstein -- Algorithmic Aspects of Secure Computation and Communication (Abstract) / Matt Franklin -- Session 1A. Approximation Algorithm I -- Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament / Marek Karpinski, Warren Schudy -- A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2 / Piotr Berman, Marek Karpinski, Alexander Zelikovsky -- Approximate Periodicity / Amihood Amir, Estrella Eisenberg, Avivit Levy -- Approximating the Average Stretch Factor of Geometric Graphs / Siu-Wing Cheng, Christian Knauer, Stefan Langerman, Michiel Smid -- Session 1B. Complexity I -- Satisfiability with Index Dependency / Hongyu Liang, Jing He -- Anonymous Fuzzy Identity-Based Encryption for Similarity Search / David W. Cheung, Nikos Mamoulis, W. K. Wong, S. M. Yiu, Ye Zhang -- Improved Randomized Algorithms for 3-SAT / Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki -- Quantum Counterfeit Coin Problems / Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Junichi Teruyama -- Session 2A. Data Structure and Algorithm I -- Priority Range Trees / Michael T. Goodrich, Darren Strash -- Should Static Search Trees Ever Be Unbalanced? / Prosenjit Bose, Karim DouIeb -- Levelwise Mesh Sparsification for Shortest Path Quaries / Yuichiro Miyamoto, Takeaki Uno, Mikio Kubo -- Unit-Time Predecessor Queries on Massive Data Sets / Andrej Brodnik, John Iacono -- Session 2B. Combinatorial Optimization -- Popularity at Minimum Cost / Telikepalli Kavitha, Meghana Nasre, Prajakta Nimbhorkar -- Structural and (Complexity Aspects of Line Systems of Graphs / Jozef JirAsek, Pavel KlavIk -- Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra / Akiyoshi Shioura -- Generating Trees on Multisets / Bingbing Zhuang, Hiroshi Nagamochi -- Session 3A. Graph Algorithm I -- Seidel Minor, Permutation Graphs and Combinatorial Properties / Vincent Limouzy -- Simultaneous Interval Graphs / Krishnam Raju Jampani, Anna Lubiw -- Unbalanced Graph Partitioning / Angsheng Li, Peng Zhang -- On the Intersection of Tolerance and Cocomparability Graphs / George B. Mertzios, Shmuel Zaks -- Flows in One-Crossing-Minor-Free Graphs / Erin Chambers, David Eppstein -- Session 3B. Complexity II -- From Holant to #CSP and Back: Dichotomy for Holantc Problems / Jin-Yi Cai, Sangxia Huang, Pinyan Lu -- Computing Sparse Multiples of Polynomials / Mark Giesbrecht, Daniel S. Roche, Hrushikesh Tilak -- Fractal Parallelism: Solving SAT in Bounded Space and Time / Denys Duchier, JErOme Durand-Lose, Maxime Senot -- Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity / Hugo FErEe, Emmanuel Hianry, Mathieu Hoyrup, Romain PEchoux -- New Upper Bounds on the Average PTF Density of Boolean Functions / Kazuyuki Amano -- Session 4A. Computational Geometry I -- An Optimal Algorithm for Computing Angle-Constrained Spanners / Paz Carmi, Michiel Smid -- Approximating Minimum Bending Energy Path in a Simple Corridor / Jinhui Xu, Lei Xu, Yulai Xie -- Session 4B. Graph Coloring I -- Analysis of an Iterated Local Search Algorithm for Vertex Coloring / Dirk Sudholt, Christine Zarges -- Bounded Max-colorings of Graphs / Evripidis Bampis, Alexander Kononov, Giorgio Lucarelli, Ioannis Milis -- Session 5A. Fixed Parameter Tractability -- Parameterized Algorithms for Boxicity / Abhijin Adiga, Rajesh Chitnis, Saket Saurabh -- On Tractable Cases of Target Set Selection / AndrE Nichterlein, Rolf Niedermeier, Johannes Uhlmann, Mathias Weller -- Combining Two Worlds: Parameterised Approximation for Vertex Cover / Ljiljana Brankovic, Henning Fernau -- Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time / David Eppstein, Maarten LOffler, Darren Strash -- Session 5B. Optimization -- Lower Bounds for Howard's Algorithm for Finding Minimum Mean-Cost Cycles / Thomas Dueholm Hansen, Uri Zwick -- Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut / Immanuel Bomze, Markus Chimani, Michael JUnger, Ivana Ljubic, Petra Mutzel, Bernd Zey -- An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems / Joachim Spoerhase -- A Faster Algorithm for the Maximum Even Factor Problem / Maxim A. Babenko -- Author Index. Publisher Marketing: This volume contains the proceedings of the 21st Annual International S- posium on Algorithms and Computations (ISAAC 2010), held in Jeju, Korea during December 15 17, 2010. Past editions have been held in Tokyo, Taipei, Nagoya, HongKong, Beijing, Cairns, Osaka, Singapore, Taejon, Chennai, Taipei, Christchurch, Vancouver, Kyoto, Hong Kong, Hainan, Kolkata, Sendai, Gold Coast, and Hawaii over the years 1990-2009. ISAACis anannualinternationalsymposiumthatcoversthe verywide range of topics in algorithms and computation. The main purpose of the symposium is to provide a forum for researchers working in algorithms and the theory of computation where they can exchange ideas in this active research community. In response to the call for papers, ISAAC 2010 received 182 papers. Each submission was reviewed by at least three Program Committee members with the assistance of external referees. Since there were many high-quality papers, the Program Committee s task was extremely di?cult. Through an extensive discussion, the Program Committee accepted 77 of the submissions to be p- sented at the conference. Two special issues, one of Algorithmica and one of the International Journal of Computational Geometry and Applications, were prepared with selected papers from ISAAC 2010. The best paper award was given to From Holant to #CSP and Back: c DichotomyforHolant Problems byJin-YiCai, SangxiaHuangandPinyanLu, and the best student paper award to Satis?ability with Index Dependency by Hongyu Liang and Jing He. Two eminent invited speakers, David Eppstein from UniversityofCalifornia, Irvine, andMattFranklinfromUniversityofCalifornia, Davis, also contributed to this volume."