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

Invited Talk

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

Approximation Algorithm I

• 
  Zeyu Guo, He Sun, Hong Zhu: Greedy Construction of 2-Approximation Minimum Manhattan Network. 4-15
• 
  Frank Kammer, Torsten Tholey: The Complexity of Minimum Convex Coloring. 16-27
• 
  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
• 
  Christian Glaßer, Christian Reitwießner, Heinz Schmitz: Multiobjective Disk Cover Admits a PTAS. 40-51

Online Algorithm

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

Data Structure and Algorithm

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

Game Theory

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

Graph Algorithm I

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

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
• 
  Joachim Kneis, Alexander Langer, Peter Rossmanith: A New Algorithm for Finding Trees with Many Leaves. 270-281
• 
  Hans L. Bodlaender, Pinar Heggernes, Yngve Villanger: Faster Parameterized Algorithms for Minimum Fill-In. 282-293
• 
  Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, Saket Saurabh: Graph Layout Problems Parameterized by Vertex Cover. 294-305
• 
  Hans L. Bodlaender, Eelko Penninkx, Richard B. Tan: A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs. 306-317

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
• 
  Paola Flocchini, Bernard Mans, Nicola Santoro: Tree Decontamination with Temporary Immunity. 330-341
• 
  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
• 
  Yoann Dieudonné, Franck Petit: Squaring the Circle with Weak Mobile Robots. 354-365

Database

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

Approximation Algorithm II

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

Computational Biology

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

Computational Geometry I

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

Complexity I

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

Computational Geometry II

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

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
• 
  Tobias Friedrich, Nils Hebbinghaus: Average Update Times for Fully-Dynamic All-Pairs Shortest Paths. 692-703
• 
  Loukas Georgiadis: Computing Frequency Dominators and Related Problems. 704-715
• 
  Shantanu Das, Beat Gfeller, Peter Widmayer: Computing Best Swaps in Optimal Tree Spanners. 716-727

Optimization

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

Routing

• 
  Basile Couëtoux, Laurent Gourvès, Jérôme Monnot, Orestis Telelis: On Labeled Traveling Salesman Problems. 776-787
• 
  Feodor F. Dragan, Martín Matamala: Navigating in a Graph by Aid of Its Spanning Tree. 788-799
• 
  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
• 
  Daniel Delling, Giacomo Nannicini: Bidirectional Core-Based Routing in Dynamic Time-Dependent Road Networks. 812-823

Graph Algorithm II

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

Complexity II

• 
  Beate Bollig, Jochen Klump: New Results on the Most Significant Bit of Integer Multiplication. 883-894
• 
  Felix G. König, Marco E. Lübbecke: Sorting with Complete Networks of Stacks. 895-906
• 
  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
• 
  Ashley Montanaro, Harumichi Nishimura, Rudy Raymond: Unbounded-Error Quantum Query Complexity. 919-930
• 
  Rusins Freivalds: Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States. 931-942