list of accepted papers for ISAAC 2006
(1) Erik Demaine, MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi.
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's
Contraction
(2) Amos Korman, David Peleg and Yoav Rodeh. Constructing Labeling Schemes
through Universal Matrices
(3) Divesh Aggarwal, Chandan Dubey and Shashank K. Mehta. Algorithms on graphs
with small dominating targets
(4) Tatsuya Akutsu, Daiji Fukagawa and Atsuhiro Takasu. Approximating Tree
Edit Distance Through String Edit Distance
(5) Kiyoko Aoki-Kinoshita, Minoru Kanehisa, Ming-Yang Kao, Xiang-Yang Li and
Weizhao Wang. A 6-Approximation Algorithm for Computing the Least Common
\aon-supertree With Application to the Reconstruction of Glycan Trees
(6) Federico Mancini, Pinar Heggernes and Charis Papadopoulos. Making
arbitrary graphs transitively orientable: Minimal comparability completions
(7) Tobias Lenz. Deterministic Splitter Finding in a Stream with Constant
Storage and Guarantees
(8) Shay Solomon and Yefim Dinitz. Optimal Algorithms for Tower of Hanoi
Problems with Relaxed Placement Rules
(9) Akira Kamada, Kazuyuki Miura and Takao Nishizeki. Convex Grid Drawings of
Plane Graphs with Rectangular Contours
(10) Sumit Ganguly and Barna Saha. On Estimating Path Aggregates over Streaming
Graphs
(11) Andris Ambainis, William Gasarch, Aravind Srinivasan and Andrey Utis.
Lower Bounds on the Deterministic and Quantum Communication Complexities of
Hamming-Distance Problems
(12) Robert Schweller, Manan Sanghi and Ming-Yang Kao. Flexible Word Design
and Graph Labeling
(13) Jussi Kujala and Tapio Elomaa. Poketree: A Dynamically Competitive Data
Structure with Good Worst-Case Performance
(14) Dirk Sudholt. Local Search in Memetic Algorithms: the Impact of the Local
Search Frequency
(15) Xiaodong Wu. Efficient Algorithms for the Optimal-Ratio Region Detection
Problems in Discrete Geometry with Applications
(16) VIkraman Arvind and Jacobo Toran. The Complexity of Quasigroup
Isomorphism and the Minimum Generating Set Problem
(17) Venkatesan Guruswami. On 2-Query Codeword Testing
(18) Martin Hoefer. Non-cooperative Facility Location and Covering Games
(19) Peter Hoyer, Mehdi Mhalla and Simon Perdrix. Resources required for
preparing graph states
(20) Gennaro Cordasco and Luisa Gargano. How Much Independent Should
Individual Contacts be to Form a Small-World?
(21) Ferdinando Cicalese, Fredrik Manne and Qin Xin. Faster Centralized
Communication in Radio Networks
(22) Sang Won Bae, Jae-Hoon Kim and Kyung-Yong Chwa. Optimal Construction of
the City Voronoi Diagram
(23) Henning Meyerhenke and Thomas Sauerwald. Analyzing Disturbed Diffusion
on Networks
(24) Telikepalli Kavitha and Chintan Shah. Efficient Algorithms for Weighted
Rank-Maximal Matchings and Related Problems
(25) Qiaosheng Shi, Binay Bhattacharya, Arie Tamir and Yuzhuang Hu. Optimal
Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees
(26) Chunmei Liu and Yinglei Song. Exact Algorithms for Finding the Minimum
Independent Dominating Set in Graphs
(27) Weimin Ma and Ke Wang. On the On-line k-Truck Problem with the Benefit
Maximization
(28) VIkraman Arvind, Bireswar Das and Partha Mukhopadhyay. On Isomorphism
and Canonization of Tournaments and Hypertournaments
(29) George Tsaggouris and Christos Zaroliagis. Multiobjective Optimization:
Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications
(30) Fabrizio Grandoni and Giuseppe Italiano. Improved Approximation for
Single-Sink Buy-at-Bulk
(31) Patrick Briest and Christian Gunia. Energy-Efficient Broadcast Scheduling
for Speed-Controlled Transmission Channels
(32) Karol Suchan and Ioan Todinca. Minimal Interval Completion Through Graph
Exploration
(33) Frank Neumann and Carsten Witt. Runtime Analysis of a Simple Ant Colony
Optimization Algorithm (Extended Abstract)
(34) Josep Diaz, Fabrizio Grandoni and Alberto Marchetti-Spaccamela. Balanced
Cut Approximation in Random Geometric Graphs
(35) Hsiao-Fei Liu and Kun-Mao Chao. On Locating Disjoint Segments with
Maximum Sum of Densities
(36) Yusu Wang. Relations between two common types of rectangular tilings
(37) Danny Z. Chen, Rudolf Fleischer, Jian Li, Zhiyi Xie and Hong Zhu. On
approximating the maximum simple sharing problem
(38) Ralf Klasing, Euripides Markou and Andrzej Pelc. Gathering asynchronous
oblivious mobile robots in a ring
(39) Serge Gaspers, Fedor Fomin and Saket Saurabh. Branching and Treewidth
Based Exact Algorithms
(40) Xinwei Shi and Ho-lun Cheng. Quality Tetrahedral Mesh Generation for
Macromolecules
(41) Takehiro Ito, Erik Demaine, Xiao Zhou and Takao Nishizeki.
Approximability of Partitioning Graphs with Supply and Demand
(42) Wun-Tat Chan, Francis Chin, Deshi Ye, Yong Zhang and Hong Zhu. Frequency
Allocation Problem for Linear Cellular Networks
(43) Khaled Elbassioni, Aleksei Fishkin and Rene Sitters. On Approximating
the TSP with intersecting Neighborhoods
(44) Amr Elmasry, Jyrki Katajainen and Claus Jensen. Two-tier relaxed heaps
(45) Tzu-Chin Lin, Hung-I Yu and Biing-Feng Wang. Improved Algorithms for the
Minmax-Regret 1-Center Problem
(46) Takashi Horiyama, Kazuo Iwama and Jun Kawahara. Finite-State Online
Algorithms and Their Automated Competitive Analysis
(47) Mikael Onsjoe and Osamu Watanabe. A Simple Message Passing Algorithm for
Graph Partition Problems
(48) Saswata Shannigrahi and Sudebkumar Prasant Pal. Efficient Prufer-like
coding and counting labelled hypertrees
(49) Michael Krueger and Harald Hempel. Inverse HAMILTONIAN CYCLE and Inverse
3-D MATCHING are coNP-complete
(50) Lukasz Kowalik. Approximation Scheme for Lowest Outdegree Orientation
and Graph Density Measures
(51) Prosenjit Bose, Michiel Smid and Daming Xu. Diamond Triangulations
Contain Spanners of Bounded Degree
(52) Guido Proietti and Peter Widmayer. Partitioning the Nodes of a Graph to
Minimize the Sum of Subgraph Radii
(53) Sylvain Guillemot. Parameterized complexity of some problems on
coincidence graphs
(54) Tien-Ching Lin and D. T. Lee. Efficient Algorithm for the Sum Selection
Problem and K Maximum Sums Problem
(55) Tobias Friedrich and Benjamin Doerr. Deterministic Random Walks on the
Two-Dimensional Grid
(56) Shirou Maruyama, Hiromitsu Miyagawa and Hiroshi Sakamoto. Improving Time
and Space Complexity for Compressed Pattern Matching
(57) Costas Iliopoulos and M Sohel Rahman. Algorithms for Computing Variants
of the Longest Common Subsequence Problem
(58) Benjamin Doerr, Johannes Lengler and David Steurer. The Interval Liar
Game
(59) Katarzyna Paluch. New approximation algorithms for multidimensional
rectangle tiling
(60) Stefan Ruhrup and Christian Schindelhauer. Online Multi-Path Routing in
a Maze
(61) Mingen Lin, Yang Yang and Jinhui Xu. Improved Approximation Algorithms
for Maximum Resource Bin Packing and Lazy Bin Covering Problems
(62) Danny Z. Chen and Chao Wang. Field Splitting Problems in
Intensity-Modulated Radiation Therapy
(63) Christian Hundt, Maciej Liskiewicz and Ulrich Woelfel. Provably Secure
Steganography and the Complexity of Sampling
(64) Danny Z. Chen, Xiaobo S. Hu, Shuang Luan, Ewa Misiolek and Chao Wang.
Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy
(65) Yunhong Zhou. Improved Multi-unit Auction Clearing Algorithms with
Interval (Multiple-Choice) Knapsack Problems
(66) Robert Elsaesser and Thomas Sauerwald. On the Runtime and Robustness of
Randomized Broadcasting
(67) Scott Dillard, Gunther Weber, Vijay Natarajan, Valerio Pascucci and Bernd
Hamann. Tessellation of Quadratic Elements
(68) Kazuo Iwama, Hiroki Morizumi and Jun Tarui. Negation-Limited Complexity
of Parity and Inverters
(69) Mohamed Aly and John Augustine. Online Packet Admission and Oblivious
Routing in Sensor Networks
(70) Shantanu Das, Paola Flocchini, Amiya Nayak and Nicola Santoro. Effective
Elections for Anonymous Mobile Agents
(71) Vinayaka Pandit and Rohit Khandekar. Offline sorting buffers on Line
(72) Allan Scott, Ulrike Stege and Norbert Zeh. Politician's Firefighting
(73) Joachim Kneis, Daniel Moelle, Stefan Richter and Peter Rossmanith.
Intuitive Algorithms and t-Vertex Cover