21. ISAAC 2010: Jeju Island, Korea

Otfried Cheong, Kyung-Yong Chwa, Kunsoo Park (Eds.): Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I. Lecture Notes in Computer Science 6506 Springer 2010, ISBN 978-3-642-17516-9

Invited Talks

David Eppstein:
Regular Labelings and Geometric Structures. 1
Matt Franklin:
Algorithmic Aspects of Secure Computation and Communication. 2

Marek Karpinski, Warren Schudy:
Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. 3-14
Piotr Berman, Marek Karpinski, Alexander Zelikovsky:
A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2. 15-24
Amihood Amir, Estrella Eisenberg, Avivit Levy:
Approximate Periodicity. 25-36
Siu-Wing Cheng, Christian Knauer, Stefan Langerman, Michiel H. M. Smid:
Approximating the Average Stretch Factor of Geometric Graphs. 37-48

Hongyu Liang, Jing He:
Satisfiability with Index Dependency. 49-60
David W. Cheung, Nikos Mamoulis, W. K. Wong, Siu-Ming Yiu, Ye Zhang:
Anonymous Fuzzy Identity-Based Encryption for Similarity Search. 61-72
Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki:
Improved Randomized Algorithms for 3-SAT. 73-84
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Junichi Teruyama:
Quantum Counterfeit Coin Problems. 85-96

Michael T. Goodrich, Darren Strash:
Priority Range Trees. 97-108
Prosenjit Bose, Karim Douïeb:
Should Static Search Trees Ever Be Unbalanced? 109-120
Yuichiro Miyamoto, Takeaki Uno, Mikio Kubo:
Levelwise Mesh Sparsification for Shortest Path Queries. 121-132
Andrej Brodnik, John Iacono:
Unit-Time Predecessor Queries on Massive Data Sets. 133-144

Telikepalli Kavitha, Meghana Nasre, Prajakta Nimbhorkar:
Popularity at Minimum Cost. 145-156
Jozef Jirásek, Pavel Klavík:
Structural and Complexity Aspects of Line Systems of Graphs. 157-168
Akiyoshi Shioura:
Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra. 169-181
Bingbing Zhuang, Hiroshi Nagamochi:
Generating Trees on Multisets. 182-193

Vincent Limouzy:
Seidel Minor, Permutation Graphs and Combinatorial Properties. 194-205
Krishnam Raju Jampani, Anna Lubiw:
Simultaneous Interval Graphs. 206-217
Angsheng Li, Peng Zhang:
Unbalanced Graph Partitioning. 218-229
George B. Mertzios, Shmuel Zaks:
On the Intersection of Tolerance and Cocomparability Graphs. 230-240
Erin W. Chambers, David Eppstein:
Flows in One-Crossing-Minor-Free Graphs. 241-252

Jin-yi Cai, Sangxia Huang, Pinyan Lu:
From Holant to #CSP and Back: Dichotomy for Holant^c Problems. 253-265
Mark Giesbrecht, Daniel S. Roche, Hrushikesh Tilak:
Computing Sparse Multiples of Polynomials. 266-278
Denys Duchier, Jérôme Durand-Lose, Maxime Senot:
Fractal Parallelism: Solving SAT in Bounded Space and Time. 279-290
Hugo Férée, Emmanuel Hainry, Mathieu Hoyrup, Romain Péchoux:
Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity. 291-303
Kazuyuki Amano:
New Upper Bounds on the Average PTF Density of Boolean Functions. 304-315

Paz Carmi, Michiel H. M. Smid:
An Optimal Algorithm for Computing Angle-Constrained Spanners. 316-327
Jinhui Xu, Lei Xu, Yulai Xie:
Approximating Minimum Bending Energy Path in a Simple Corridor. 328-339

Dirk Sudholt, Christine Zarges:
Analysis of an Iterated Local Search Algorithm for Vertex Coloring. 340-352
Evripidis Bampis, Alexander Kononov, Giorgio Lucarelli, Ioannis Milis:
Bounded Max-colorings of Graphs. 353-365

Abhijin Adiga, Rajesh Hemant Chitnis, Saket Saurabh:
Parameterized Algorithms for Boxicity. 366-377
André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, Mathias Weller:
On Tractable Cases of Target Set Selection. 378-389
Ljiljana Brankovic, Henning Fernau:
Combining Two Worlds: Parameterised Approximation for Vertex Cover. 390-402
David Eppstein, Maarten Löffler, Darren Strash:
Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. 403-414

Thomas Dueholm Hansen, Uri Zwick:
Lower Bounds for Howard's Algorithm for Finding Minimum Mean-Cost Cycles. 415-426
Immanuel M. Bomze, Markus Chimani, Michael Jünger, Ivana Ljubic, Petra Mutzel, Bernd Zey:
Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut. 427-439
Joachim Spoerhase:
An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems. 440-450
Maxim A. Babenko:
A Faster Algorithm for the Maximum Even Factor Problem. 451-462

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