19. ISAAC 2008: Gold Coast, Australia

Seok-Hee Hong, Hiroshi Nagamochi, Takuro Fukunaga (Eds.): Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings. Lecture Notes in Computer Science 5369 Springer 2008, ISBN 978-3-540-92181-3 BibTeX

Invited Talk

Tetsuo Asano:
Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?. 1
Electronic Edition (link) BibTeX
Peter Eades:
Some Constrained Notions of Planarity. 2
Electronic Edition (link) BibTeX
Robert Endre Tarjan:
Reachability Problems on Directed Graphs. 3
Electronic Edition (link) BibTeX

Approximation Algorithm I

Zeyu Guo, He Sun, Hong Zhu:
Greedy Construction of 2-Approximation Minimum Manhattan Network. 4-15
Electronic Edition (link) BibTeX
Frank Kammer, Torsten Tholey:
The Complexity of Minimum Convex Coloring. 16-27
Electronic Edition (link) BibTeX
Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno:
On the Complexity of Reconfiguration Problems. 28-39
Electronic Edition (link) BibTeX
Christian Glaßer, Christian Reitwießner, Heinz Schmitz:
Multiobjective Disk Cover Admits a PTAS. 40-51
Electronic Edition (link) BibTeX

Online Algorithm

Sumit Ganguly:
Data Stream Algorithms via Expander Graphs. 52-63
Electronic Edition (link) BibTeX
Shuichi Miyazaki, Kazuya Okamoto:
Improving the Competitive Ratio of the Online OVSF Code Assignment Problem. 64-76
Electronic Edition (link) BibTeX
Weiwei Wu, Minming Li, Enhong Chen:
Optimal Key Tree Structure for Deleting Two or More Leaves. 77-88
Electronic Edition (link) BibTeX
Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, Rodica Mihai:
Comparing First-Fit and Next-Fit for Online Edge Coloring. 89-99
Electronic Edition (link) BibTeX

Data Structure and Algorithm

Gerth Stølting Brodal, Allan Grønlund Jørgensen:
Selecting Sums in Arrays. 100-111
Electronic Edition (link) BibTeX
Craig Dillabaugh, Meng He, Anil Maheshwari:
Succinct and I/O Efficient Data Structures for Traversal in Trees. 112-123
Electronic Edition (link) BibTeX
Simon J. Puglisi, Andrew Turpin:
Space-Time Tradeoffs for Longest-Common-Prefix Array Computation. 124-135
Electronic Edition (link) BibTeX
Daniel Raible, Henning Fernau:
Power Domination in O^*(1.7548ⁿ) Using Reference Search Trees. 136-147
Electronic Edition (link) BibTeX

Game Theory

Yingchao Zhao, Wei Chen, Shang-Hua Teng:
The Isolation Game: A Game of Distances. 148-158
Electronic Edition (link) BibTeX
Evangelos Bampas, Aris Pagourtzis, George Pierrakos, Katerina Potika:
On a Non-cooperative Model for Wavelength Assignment in Multifiber Optical Networks. 159-170
Electronic Edition (link) BibTeX
Shankar Kalyanaraman, Christopher Umans:
The Complexity of Rationalizing Matchings. 171-182
Electronic Edition (link) BibTeX
Panagiota N. Panagopoulou, Paul G. Spirakis:
A Game Theoretic Approach for Efficient Graph Coloring. 183-195
Electronic Edition (link) BibTeX

Graph Algorithm I

Takehiro Ito, Takeaki Uno, Xiao Zhou, Takao Nishizeki:
Partitioning a Weighted Tree to Subtrees of Almost Uniform Size. 196-207
Electronic Edition (link) BibTeX
Mingyu Xiao:
An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts. 208-219
Electronic Edition (link) BibTeX
Michael Lampis, Georgia Kaouri, Valia Mitsou:
On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures. 220-231
Electronic Edition (link) BibTeX
Maxim A. Babenko:
An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem. 232-245
Electronic Edition (link) BibTeX
Yuta Harada, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita:
The Balanced Edge Cover Problem. 246-257
Electronic Edition (link) BibTeX

Fixed Parameter Tractability

Leizhen Cai, Elad Verbin, Lin Yang:
Firefighting on Trees: (1-1/e)-Approximation, Fixed Parameter Tractability and a Subexponential Algorithm. 258-269
Electronic Edition (link) BibTeX
Joachim Kneis, Alexander Langer, Peter Rossmanith:
A New Algorithm for Finding Trees with Many Leaves. 270-281
Electronic Edition (link) BibTeX
Hans L. Bodlaender, Pinar Heggernes, Yngve Villanger:
Faster Parameterized Algorithms for Minimum Fill-In. 282-293
Electronic Edition (link) BibTeX
Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, Saket Saurabh:
Graph Layout Problems Parameterized by Vertex Cover. 294-305
Electronic Edition (link) BibTeX
Hans L. Bodlaender, Eelko Penninkx, Richard B. Tan:
A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs. 306-317
Electronic Edition (link) BibTeX

Distributed Algorithm

Fedor V. Fomin, Petr A. Golovach, Alexander Hall, Matús Mihalák, Elias Vicari, Peter Widmayer:
How to Guard a Graph?. 318-329
Electronic Edition (link) BibTeX
Paola Flocchini, Bernard Mans, Nicola Santoro:
Tree Decontamination with Temporary Immunity. 330-341
Electronic Edition (link) BibTeX
Greg Aloupis, Sébastien Collette, Erik D. Demaine, Stefan Langerman, Vera Sacristán Adinolfi, Stefanie Wuhrer:
Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves. 342-353
Electronic Edition (link) BibTeX
Yoann Dieudonné, Franck Petit:
Squaring the Circle with Weak Mobile Robots. 354-365
Electronic Edition (link) BibTeX

Database

Ehsan Chiniforooshan, Arash Farzan, Mehdi Mirzazadeh:
Evaluation of General Set Expressions. 366-377
Electronic Edition (link) BibTeX
Ferdinando Cicalese, Martin Milanic:
Computing with Priced Information: When the Value Makes the Price. 378-389
Electronic Edition (link) BibTeX
Kazuhisa Makino, Hirotaka Ono:
Deductive Inference for the Interiors and Exteriors of Horn Theories. 390-401
Electronic Edition (link) BibTeX
Michael R. Fellows, Daniel Meister, Frances A. Rosamond, R. Sritharan, Jan Arne Telle:
Leaf Powers and Their Properties: Using the Trees. 402-413
Electronic Edition (link) BibTeX

Approximation Algorithm II

Ali Civril, Malik Magdon-Ismail:
Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD. 414-423
Electronic Edition (link) BibTeX
Naveen Garg, Amit Kumar, V. N. Muralidhara:
Minimizing Total Flow-Time: The Unrelated Case. 424-435
Electronic Edition (link) BibTeX
Karl Bringmann, Tobias Friedrich:
Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects. 436-447
Electronic Edition (link) BibTeX
Christian Glaßer:
Space-Efficient Informational Redundancy. 448-459
Electronic Edition (link) BibTeX

Computational Biology

Cheng-Wei Luo, Hsiao-Fei Liu, Peng-An Chen, Kun-Mao Chao:
Minkowski Sum Selection and Finding. 460-471
Electronic Edition (link) BibTeX
Leo van Iersel, Steven Kelk:
Constructing the Simplest Possible Phylogenetic Network from Triplets. 472-483
Electronic Edition (link) BibTeX
Jaroslaw Byrka, Sylvain Guillemot, Jesper Jansson:
New Results on Optimizing Rooted Triplets Consistency. 484-495
Electronic Edition (link) BibTeX
M. Oguzhan Külekci:
A Method to Overcome Computer Word Size Limitation in Bit-Parallel Pattern Matching. 496-506
Electronic Edition (link) BibTeX

Computational Geometry I

Ludmila Scharf, Marc Scherfenberg:
Inducing Polygons of Line Arrangements. 507-519
Electronic Edition (link) BibTeX
Danny Z. Chen, Ewa Misiolek:
Free-Form Surface Partition in 3-D. 520-531
Electronic Edition (link) BibTeX
Christian Knauer, Marc Scherfenberg:
Approximate Nearest Neighbor Search under Translation Invariant Hausdorff Distance. 532-543
Electronic Edition (link) BibTeX
Marc J. van Kreveld, Maarten Löffler, Joseph S. B. Mitchell:
Preprocessing Imprecise Points and Splitting Triangulations. 544-555
Electronic Edition (link) BibTeX
Harish Doraiswamy, Vijay Natarajan:
Efficient Output-Sensitive Construction of Reeb Graphs. 556-567
Electronic Edition (link) BibTeX

Complexity I

Jin-yi Cai, Pinyan Lu:
Signature Theory in Holographic Algorithms. 568-579
Electronic Edition (link) BibTeX
David Buchfuhrer:
The Complexity of SPP Formula Minimization. 580-591
Electronic Edition (link) BibTeX
Eric Goles Ch., Cedric Little, Ivan Rapaport:
Understanding a Non-trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol. 592-604
Electronic Edition (link) BibTeX
Hiroki Morizumi, Genki Suzuki:
Negation-Limited Inverters of Linear Size. 605-614
Electronic Edition (link) BibTeX
Giovanni Di Crescenzo, Helger Lipmaa:
3-Message NP Arguments in the BPK Model with Optimal Soundness and Zero-Knowledge. 615-627
Electronic Edition (link) BibTeX

Computational Geometry II

Jonathan Backer, David G. Kirkpatrick:
A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths. 628-643
Electronic Edition (link) BibTeX
Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler, Jun Luo:
Detecting Commuting Patterns by Clustering Subtrajectories. 644-655
Electronic Edition (link) BibTeX
Prosenjit Bose, Paz Carmi, Sébastien Collette, Michiel H. M. Smid:
On the Stretch Factor of Convex Delaunay Graphs. 656-667
Electronic Edition (link) BibTeX
Hee-Kap Ahn, Peter Brass, Christian Knauer, Hyeon-Suk Na, Chan-Su Shin:
Covering a Simple Polygon by Monotone Directions. 668-679
Electronic Edition (link) BibTeX

Network

Reid Andersen, Christian Borgs, Jennifer T. Chayes, John E. Hopcroft, Vahab S. Mirrokni, Shang-Hua Teng:
On the Stability of Web Crawling and Web Search. 680-691
Electronic Edition (link) BibTeX
Tobias Friedrich, Nils Hebbinghaus:
Average Update Times for Fully-Dynamic All-Pairs Shortest Paths. 692-703
Electronic Edition (link) BibTeX
Loukas Georgiadis:
Computing Frequency Dominators and Related Problems. 704-715
Electronic Edition (link) BibTeX
Shantanu Das, Beat Gfeller, Peter Widmayer:
Computing Best Swaps in Optimal Tree Spanners. 716-727
Electronic Edition (link) BibTeX

Optimization

Hee-Kap Ahn, Sang Won Bae:
Covering a Point Set by Two Disjoint Rectangles. 728-739
Electronic Edition (link) BibTeX
Christian Wulff-Nilsen:
Computing the Maximum Detour of a Plane Graph in Subquadratic Time. 740-751
Electronic Edition (link) BibTeX
Harold N. Gabow, Shuxin Nie:
Finding Long Paths, Cycles and Circuits. 752-763
Electronic Edition (link) BibTeX
Jun Luo, Christian Wulff-Nilsen:
Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces. 764-775
Electronic Edition (link) BibTeX

Routing

Basile Couëtoux, Laurent Gourvès, Jérôme Monnot, Orestis Telelis:
On Labeled Traveling Salesman Problems. 776-787
Electronic Edition (link) BibTeX
Feodor F. Dragan, Martín Matamala:
Navigating in a Graph by Aid of Its Spanning Tree. 788-799
Electronic Edition (link) BibTeX
Binay K. Bhattacharya, Paz Carmi, Yuzhuang Hu, Qiaosheng Shi:
Single Vehicle Scheduling Problems on Path/Tree/Cycle Networks with Release and Handling Times. 800-811
Electronic Edition (link) BibTeX
Daniel Delling, Giacomo Nannicini:
Bidirectional Core-Based Routing in Dynamic Time-Dependent Road Networks. 812-823
Electronic Edition (link) BibTeX

Graph Algorithm II

Ryuhei Uehara:
Bandwidth of Bipartite Permutation Graphs. 824-835
Electronic Edition (link) BibTeX
Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar:
König Deletion Sets and Vertex Covers above the Matching Size. 836-847
Electronic Edition (link) BibTeX
Andreas Brandstädt, Tilo Klembt, Vadim V. Lozin, Raffaele Mosca:
Independent Sets of Maximum Weight in Apple-Free Graphs. 848-858
Electronic Edition (link) BibTeX
Yasuko Matsui, Ryuhei Uehara, Takeaki Uno:
Enumeration of Perfect Sequences of Chordal Graph. 859-870
Electronic Edition (link) BibTeX
Vadim V. Lozin:
From Tree-Width to Clique-Width: Excluding a Unit Interval Graph. 871-882
Electronic Edition (link) BibTeX

Complexity II

Beate Bollig, Jochen Klump:
New Results on the Most Significant Bit of Integer Multiplication. 883-894
Electronic Edition (link) BibTeX
Felix G. König, Marco E. Lübbecke:
Sorting with Complete Networks of Stacks. 895-906
Electronic Edition (link) BibTeX
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita:
Quantum Query Complexity of Boolean Functions with Small On-Sets. 907-918
Electronic Edition (link) BibTeX
Ashley Montanaro, Harumichi Nishimura, Rudy Raymond:
Unbounded-Error Quantum Query Complexity. 919-930
Electronic Edition (link) BibTeX
Rusins Freivalds:
Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States. 931-942
Electronic Edition (link) BibTeX