18. ISAAC 2007: Sendai, Japan

Takeshi Tokuyama (Ed.): Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings. Lecture Notes in Computer Science 4835 Springer 2007, ISBN 978-3-540-77118-0 BibTeX

Invited Talk

Pankaj K. Agarwal:
Modeling and Analyzing Massive Terrain Data Sets. 1
Electronic Edition (link) BibTeX
Zdenek Dvorak, Daniel Král, Robin Thomas:
Coloring Triangle-Free Graphs on Surfaces. 2-4
Electronic Edition (link) BibTeX

Best Paper Award Presentation

M. Ziaur Rahman, J. Ian Munro:
Integer Representation and Counting in the Bit Probe Model. 5-16
Electronic Edition (link) BibTeX

Graph Algorithms I

Hiroshi Nagamochi:
Minimum Degree Orderings. 17-28
Electronic Edition (link) BibTeX
Toshimasa Ishii:
Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs. 29-40
Electronic Edition (link) BibTeX
Emeric Gioan, Christophe Paul:
Dynamic Distance Hereditary Graphs Using Split Decomposition. 41-51
Electronic Edition (link) BibTeX
Binh-Minh Bui-Xuan, Michel Habib, Vincent Limouzy, Fabien de Montgolfier:
Unifying Two Graph Decompositions with Modular Decomposition. 52-64
Electronic Edition (link) BibTeX

Computational Geometry I

Peter Brass, Kyue D. Kim, Hyeon-Suk Na, Chan-Su Shin:
Escaping Off-Line Searchers and a Discrete Isoperimetric Theorem. 65-74
Electronic Edition (link) BibTeX
Yang Yang, Yongding Zhu, Jinhui Xu, Naoki Katoh:
Geometric Spanner of Segments. 75-87
Electronic Edition (link) BibTeX
Hee-Kap Ahn, Mohammad Farshi, Christian Knauer, Michiel H. M. Smid, Yajun Wang:
Dilation-Optimal Edge Deletion in Polygonal Cycles. 88-99
Electronic Edition (link) BibTeX

Complexity I

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita:
Unbounded-Error Classical and Quantum Communication Complexity. 100-111
Electronic Edition (link) BibTeX
Masaki Yamamoto:
A Spectral Method for MAX2SAT in the Planted Solution Model. 112-123
Electronic Edition (link) BibTeX
Uffe Flarup, Pascal Koiran, Laurent Lyaudet:
On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices. 124-136
Electronic Edition (link) BibTeX
Rahul Tripathi:
The 1-Versus-2 Queries Problem Revisited. 137-147
Electronic Edition (link) BibTeX

Graph Drawing

Petr Hlinený, Gelasio Salazar:
Approximating the Crossing Number of Toroidal Graphs. 148-159
Electronic Edition (link) BibTeX
Jia-Hao Fan, Chun-Cheng Lin, Hsueh-I Lu, Hsu-Chun Yen:
Width-Optimal Visibility Representations of Plane Graphs. 160-171
Electronic Edition (link) BibTeX
Francesco Giordano, Giuseppe Liotta, Tamara Mchedlidze, Antonios Symvonis:
Computing Upward Topological Book Embeddings of Upward Planar Digraphs. 172-183
Electronic Edition (link) BibTeX
Markus Chimani, Carsten Gutwenger:
Algorithms for the Hypergraph and the Minor Crossing Number Problems. 184-195
Electronic Edition (link) BibTeX

Distributed Algorithms

Thomas Sauerwald:
On Mixing and Edge Expansion Properties in Randomized Broadcasting. 196-207
Electronic Edition (link) BibTeX
Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Y. Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristán Adinolfi, Stefanie Wuhrer:
Linear Reconfiguration of Cube-Style Modular Robots. 208-219
Electronic Edition (link) BibTeX
Artur Czumaj, Xin Wang:
Fast Message Dissemination in Random Geometric Ad-Hoc Radio Networks. 220-231
Electronic Edition (link) BibTeX
Martin Farach-Colton, Miguel A. Mosteiro:
Sensor Network Gossiping or How to Break the Broadcast Lower Bound. 232-243
Electronic Edition (link) BibTeX
Darin Goldstein, Kojiro Kobayashi:
On the Complexity of the "Most General" Undirected Firing Squad Synchronization Problem. 244-255
Electronic Edition (link) BibTeX

Optimization I

Mong-Jen Kao, Chung-Shou Liao:
Capacitated Domination Problem. 256-267
Electronic Edition (link) BibTeX
Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar, C. R. Subramanian:
The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number. 268-279
Electronic Edition (link) BibTeX
Xuzhen Xie, Mutsunori Yagiura, Takao Ono, Tomio Hirata, Uri Zwick:
New Bounds for the Nearly Equitable Edge Coloring Problem. 280-291
Electronic Edition (link) BibTeX
Ehab Morsy, Hiroshi Nagamochi:
Approximation to the Minimum Cost Edge Installation Problem. 292-303
Electronic Edition (link) BibTeX
Zachary Friggstad, Mohammad R. Salavatipour:
Approximability of Packing Disjoint Cycles. 304-315
Electronic Edition (link) BibTeX

Data Structure I

Jérémy Barbay, Luca Castelli Aleardi, Meng He, J. Ian Munro:
Succinct Representation of Labeled Graphs. 316-328
Electronic Edition (link) BibTeX
Mordecai J. Golin, Jian Li:
More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding. 329-340
Electronic Edition (link) BibTeX
Stephane Durocher, Christophe Paul:
Kinetic Maintenance of Mobile k-Centres on Trees. 341-352
Electronic Edition (link) BibTeX
Michael T. Goodrich, Jonathan Z. Sun:
Checking Value-Sensitive Data Structures in Sublinear Space. 353-364
Electronic Edition (link) BibTeX

Game Theory

Raphael Eidenbenz, Yvonne Anne Oswald, Stefan Schmid, Roger Wattenhofer:
Manipulation in Games. 365-376
Electronic Edition (link) BibTeX
Chien-Chung Huang, Ming-Yang Kao, Xiang-Yang Li, Weizhao Wang:
Using Nash Implementation to Achieve Better Frugality Ratios. 377-389
Electronic Edition (link) BibTeX
Vittorio Bilò:
The Price of Nash Equilibria in Multicast Transmissions Games. 390-401
Electronic Edition (link) BibTeX

Database Applications

Takeaki Uno:
An Efficient Algorithm for Enumerating Pseudo Cliques. 402-414
Electronic Edition (link) BibTeX
Samuel Guilbault, Andrzej Pelc:
Fast Adaptive Diagnosis with a Minimum Number of Tests. 415-426
Electronic Edition (link) BibTeX
Jiang Chen, Ke Yi:
Dynamic Structures for Top- k Queries on Uncertain Data. 427-438
Electronic Edition (link) BibTeX
Avrim Blum, Amin Coja-Oghlan, Alan M. Frieze, Shuheng Zhou:
Separating Populations with Wide Data: A Spectral Analysis. 439-451
Electronic Edition (link) BibTeX

Online Algorithms

Francis Y. L. Chin, Hing-Fung Ting, Yong Zhang:
A Constant-Competitive Algorithm for Online OVSF Code Assignment. 452-463
Electronic Edition (link) BibTeX
Deepak Ajwani, Tobias Friedrich:
Average-Case Analysis of Online Topological Ordering. 464-475
Electronic Edition (link) BibTeX
Tak Wah Lam, Lap-Kei Lee, Isaac Kar-Keung To, Prudence W. H. Wong:
Energy Efficient Deadline Scheduling in Two Processor Systems. 476-487
Electronic Edition (link) BibTeX
Reza Dorrigiv, Alejandro López-Ortiz, J. Ian Munro:
On the Relative Dominance of Paging Algorithms. 488-499
Electronic Edition (link) BibTeX

I/O Algorithms

Mark de Berg, Herman J. Haverkort, Shripad Thite, Laura Toma:
I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions. 500-511
Electronic Edition (link) BibTeX
Eric Y. Chen:
Geometric Streaming Algorithms with a Sorting Primitive. 512-524
Electronic Edition (link) BibTeX
Yakov Nekrich:
External Memory Range Reporting on a Grid. 525-535
Electronic Edition (link) BibTeX
Micha Streppel, Ke Yi:
Approximate Range Searching in External Memory. 536-548
Electronic Edition (link) BibTeX

Networks

Qin Xin:
Faster Treasure Hunt and Better Strongly Universal Exploration Sequences. 549-560
Electronic Edition (link) BibTeX
Omid Amini, Stéphane Pérennes, Ignasi Sau:
Hardness and Approximation of Traffic Grooming. 561-573
Electronic Edition (link) BibTeX
David Barbella, George Kachergis, David Liben-Nowell, Anna Sallstrom, Ben Sowell:
Depth of Field and Cautious-Greedy Routing in Social Networks. 574-586
Electronic Edition (link) BibTeX
Davide Bilò, Jörg Derungs, Luciano Gualà, Guido Proietti, Peter Widmayer:
Locating Facilities on a Network to Minimize Their Average Service Radius. 587-598
Electronic Edition (link) BibTeX

Optimization II

Anna Urbanska:
Faster Combinatorial Algorithms for Determinant and Pfaffian. 599-608
Electronic Edition (link) BibTeX
Yoshio Okamoto, Takeaki Uno:
A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization. 609-620
Electronic Edition (link) BibTeX
Hannes Moser, Venkatesh Raman, Somnath Sikdar:
The Parameterized Complexity of the Unique Coverage Problem. 621-631
Electronic Edition (link) BibTeX
Tommy Färnqvist, Peter Jonsson:
Bounded Tree-Width and CSP-Related Problems. 632-643
Electronic Edition (link) BibTeX

Computational Geometry II

Paz Carmi, Matthew J. Katz, Nissan Lev-Tov:
Covering Points by Unit Disks of Fixed Location. 644-655
Electronic Edition (link) BibTeX
Magdalene G. Borgelt, Marc J. van Kreveld, Jun Luo:
Geodesic Disks and Clustering in a Simple Polygon. 656-667
Electronic Edition (link) BibTeX
Anil Maheshwari, Doron Nussbaum, Jörg-Rüdiger Sack, Jiehua Yi:
An O ( n ²log n ) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane. 668-680
Electronic Edition (link) BibTeX
Boris Aronov, Tetsuo Asano, Stefan Funke:
Optimal Triangulation with Steiner Points. 681-691
Electronic Edition (link) BibTeX

Geometric Applications

Xiaodong Wu, Xin Dou, John E. Bayouth, John M. Buatti:
New Algorithm for Field Splitting in Radiation Therapy. 692-703
Electronic Edition (link) BibTeX
Tetsuo Asano, Shinnya Bitou, Mitsuo Motoki, Nobuaki Usui:
In-Place Algorithm for Image Rotation. 704-715
Electronic Edition (link) BibTeX
Evanthia Papadopoulou:
Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction. 716-727
Electronic Edition (link) BibTeX

Data Structures II

Cyril Gavoille, Arnaud Labourel:
Distributed Relationship Schemes for Trees. 728-738
Electronic Edition (link) BibTeX
Philip Bille, Anna Pagh, Rasmus Pagh:
Fast Evaluation of Union-Intersection Expressions. 739-750
Electronic Edition (link) BibTeX
Sung Eun Bae, Tadao Takaoka:
A Sub-cubic Time Algorithm for the k -Maximum Subarray Problem. 751-762
Electronic Edition (link) BibTeX

Computational Geometry III

Joachim Gudmundsson, Jyrki Katajainen, Damian Merrick, Cahya Ong, Thomas Wolle:
Compressing Spatio-temporal Trajectories. 763-775
Electronic Edition (link) BibTeX
Marc Benkert, Bojan Djordjevic, Joachim Gudmundsson, Thomas Wolle:
Finding Popular Places. 776-787
Electronic Edition (link) BibTeX
Sang Won Bae, Chunseok Lee, Hee-Kap Ahn, Sunghee Choi, Kyung-Yong Chwa:
Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations. 788-799
Electronic Edition (link) BibTeX

Complexity II

Vikraman Arvind, Partha Mukhopadhyay:
The Monomial Ideal Membership Problem and Polynomial Identity Testing. 800-811
Electronic Edition (link) BibTeX
Satoshi Tayu, Shigeru Ito, Shuichi Ueno:
On the Fault Testing for Reversible Circuits. 812-821
Electronic Edition (link) BibTeX
Vikraman Arvind, Bireswar Das, Johannes Köbler:
The Space Complexity of k -Tree Isomorphism. 822-833
Electronic Edition (link) BibTeX

String

Hsiao-Fei Liu, Peng-An Chen, Kun-Mao Chao:
Algorithms for Computing the Length-Constrained Max-Score Segments with Applications to DNA Copy Number Data Analysis. 834-845
Electronic Edition (link) BibTeX
Tak Wah Lam, Wing-Kin Sung, Siu-Lung Tam, Siu-Ming Yiu:
Space Efficient Indexes for String Matching with Don't Cares. 846-857
Electronic Edition (link) BibTeX
Ferdinando Cicalese, José Augusto Amgarten Quitzau:
2-Stage Fault Tolerant Interval Group Testing. 858-868
Electronic Edition (link) BibTeX
Ohad Lipsky, Benny Porat, Ely Porat, B. Riva Shalom, Asaf Tsur:
Approximate String Matching with Swap and Mismatch. 869-880
Electronic Edition (link) BibTeX

Graph Algorithms II

Federico Mancini:
Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs. 881-892
Electronic Edition (link) BibTeX
Emgad H. Bachoore, Hans L. Bodlaender:
Weighted Treewidth Algorithmic Techniques and Results. 893-903
Electronic Edition (link) BibTeX
Emanuele G. Fusco, Angelo Monti:
Spanning Trees with Many Leaves in Regular Bipartite Graphs. 904-914
Electronic Edition (link) BibTeX
Jiong Guo:
Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs. 915-926
Electronic Edition (link) BibTeX