ISAAC 2004 accepted papers

[rudolf at cs.ust.hk]

The following papers (in random order) were accepted at ISAAC 2004:

1. Xujin Chen, Wenan Zang: An Efficient Algorithm for Finding Maximum
Cycle Packings in Reducible Flow Graphs
2. Boris Aronov, Tetsuo Asano , Naoki Katoh, Kurt Mehlhorn, Takeshi
Tokuyama : Polyline Fitting of Planar Points under Min-Sum Criteria
3. Gruia Calinescu: On approximation algorithms and truthful mechanisms
4. Marcus Brazil, Pawel Winter, Martin Zachariasen: Flexibility of Steiner
Trees in Uniform Orientation Metrics
5. Ryuhei Uehara: Canonical Data Structure for Interval Probe Graphs
6. Egon Wanke: Oriented Paths in Mixed Graphs
7. Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos: Poly-APX- and
PTAS-completeness in standard and differential approximation
8. Uri Zwick: A Slightly Improved Sub-Cubic Algorithm for the All Pairs
Shortest Paths Problem with Real Edge Lengths
9. Lusheng Wang, Liang Dong , Hui Fan: Randomized Algorithms for Motif
Detection
10. Artur Pessoa, Eduardo Laber, Criston Souza: Efficient Algorithms for
the Hotlink Assignment Problem: the worst case search
11. John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba Toth:
Adaptive Spatial Partitioning for Multidimensional Data Streams
12. Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas Nandy, Shinji
Sasahara, Takeaki Uno: A Generalization of Magic Squares with Applications
to Digital Halftoning
13. Ryuhei Uehara, Yushi Uno: Efficient Algorithms for the Longest Path
Problem
14. Jesper Jansson, Wing-Kin Sung: The Maximum Agreement of Two Nested
Phylogenetic Networks
15. Kazuyuki Miura, Hiroki Haga, Takao Nishizeki: Inner Rectangular
Drawings of Plane Graphs
16. Satoshi Fujita, Toru Araki: Three-Round Adaptive Diagnosis in Binary
n-Cubes
17. Dariusz Kowalski, Andrzej Pelc: Polynomial deterministic rendezvous in
arbitrary graphs
18. Davide Bilo, Guido Proietti: Augmenting the Edge-Connectivity of a
Spider Tree
19. Dominique De Werra, Marc Demange, Bruno Escoffier, Jerome Monnot,
Vangelis Th. Paschos: Weighted coloring on planar, bipartite and split
graphs : complexity and improved approximation
20. Danny Chen, Xiaobo Hu, Shuang Luan, Shahid Naqvi, Chao Wang, Cedric
Yu: Generalized Geometric Approaches for Leaf Sequencing Problems in
Radiation Therapy
21. Michael Dom, Jiong Guo, Falk Hueffner, Rolf Niedermeier: Error
Compensation in Leaf Root Problems
22. Joachim von zur Gathen, Igor Shparlinski: GCD of Random Linear Forms
23. Artur Pessoa: Planning the Transportation of Multiple Commodities in
Bidirectional Pipeline Networks
24. Xuehou Tan: The two-guard problem revisited and its generalization
25. Bin Fu, Richard Beigel: Diagnosis in the Presence of Intermittent Faults
26. Minghui Jiang, Binhai Zhu, Sergey Bereg, Zhongping Qin: New bounds on
map labeling with circular labels
27. Peter Hui, Marcus Schaefer: Paired Pointset Traversal
28. Jun Luo, Ovidiu Daescu: Cutting Out Polygons with Lines and Rays
29. Ulrik Brandes, Juergen Lerner: Structural Similarity in Graphs (A
Relaxation Approach for Role Assignment)
30. Amitai Armon, Uri Zwick: Multicriteria Global Minimum Cuts
31. Hanno Lefmann: Distributions of Points and Large Quadrangles
32. Ming-Deh Huang: On partial lifting and the elliptic curve discrete
logarithm problem
33. Sang Won Bae, Kyung-Yong Chwa: Voronoi Diagrams with a Transportation
Network on the Euclidean Plane
34. Christian Schindelhauer, Klaus Volbert, Martin Ziegler: Spanners, Weak
Spanners, and Power Spanners for Wireless Networks
35. Jin-Yi Cai, Osamu Watanabe: Random Access to Advice Strings and
Collapsing Results
36. Jesper Jansson, Trung Hieu Ngo, Wing-Kin Sung: Local Gapped Subforest
Alignment and Its Application in Finding RNA Structural Motifs
37. Hiroshi Nagamochi, Taizo Kawada: Approximating the Minmax Subtree
Cover Problem in a Cactus
38. Kuan-Yu Chen, Kun-Mao Chao: On the Range Maximum-Sum Segment Query
Problem
39. Qingmin Shi, Joseph JaJa: Techniques for Indexing and Querying
Temporal Observations for a Collection of Objects
40. Feodor F. Dragan, Irina Lomonosov: On Compact and Efficient Routing in
Certain Graph Classes
41. Jung-Heum Park, Hee-Chul Kim, Hyeong-Seok Lim: Many-to-many disjoint
path covers in a graph with faulty elements
42. Marcus Raitner: Dynamic Tree Cross Products
43. Markus Bauer, Gunnar W. Klau: Structural Alignment of Two RNA
Sequences with Lagrangian Relaxation
44. Hsin-Fu Chen, Maw-Shang Chang: An efficient exact algorithm for the
minimum ultrametric tree problem
45. Timo von Oertzen: Exact computation of Polynomial Zeros expressible by
Square Roots
46. Daiji Fukagawa, Tatsuya Akutsu: Fast Algorithm for Comparison of
Similar Unordered Trees
47. Igor Nor: Generalized Function Matching
48. Sergey Bereg: Equipartitions of measures by 2-fans
49. Gruia Calinescu, Alexander Zelikovsky: The Polymatroid Steiner Problems
50. Mattias Andersson, Joachim Gudmundsson, Christos Levcopoulos:
Approximate Distance Oracles for Graphs with Dense Clusters
51. Mordecai Golin, Yiu Cho Leung, Yajun Wang: Counting Spanning Trees and
Other Structures in Non-Constant-Jump Circulant Graphs
52. Wun-Tat Chan, Prudence W. H. Wong: On-line Windows Scheduling and Unit
Fraction Bin Packing of Temporary Items
53. H. K. Dai, H. C. Su: On $p$-Norm Based Locality Measures of
Space-Filling Curves
54. Fredrik Bengtsson, Jingsen Chen: Efficient Algorithms for k Maximum Sums
55. Timothy M. Chan, Bashir S. Sadjad: Geometric Optimization Problems
over Sliding Windows
56. David Abraham, Katarina Cechlarova, David Manlove, Kurt Mehlhorn:
Pareto-optimality in house allocation problems
57. Zhe Dang, Oscar Ibarra, Jianwen Su: Composability of Infinite-State
Activity Automata
58. Kyung-Yong Chwa, Byung-Cheol Jo, Christian Knauer, Esther Moet, Rene
van Oostrum, Chan-Su Shin: Guarding Art Galleries by Guarding Witnesses
59. Avraham Goldstein, Petr Kolman, Jie Zheng: Minimum Common String
Partition Problem: Hardness and Approximations
60. Jae-Hoon Kim: Optimal Buffer Management via Resource Augmentation
61. Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu:
Property-Preserving Data Reconstruction
62. Zhenming Chen, Vikas Singh, Jinhui Xu: Efficient Job Scheduling
Algorithms with Multi-Type Contentions
63. Darin Goldstein, Kojiro Kobayashi: On the Complexity of Network
Synchronization
64. Kazuyuki Amano, Akira Maruoka: On the Monotone Circuit Complexity of
Quadratic Boolean Functions
65. Richard J. Nowakowski, Norbert Zeh: Boundary-Optimal Triangulation
Flooding
66. Joseph JaJa, Christian Mortensen, Qingmin Shi: Space-Efficient and
Fast Algorithms for Multidimensional Dominance Reporting and Counting
67. Zeshan Peng, Hingfung Ting: An O(nlog n)-time algorithm for the
maximum constrained agreement subtree problem for binary trees
68. Kazuo Iwama, Akinori Kawachi: Approximated Two Choices in Randomized
Load Balancing
69. Boting Yang, Danny Dyer, Brian Alspach: Sweeping graphs with large
clique number
70. Jerzy W. Jaromczyk, Zbigniew Lonc: Sequences of radius $k$: how to
fetch many huge objects into small memory for pairwise computations
71. Andreas Goerdt, Andre Lanka: On the hardness and easiness of random
4-SAT formulas
72. Vittorio Bilo, Michele Flammini, Giovanna Melideo, Luca Moscardelli:
On Nash Equilibria for Multicast Transmissions in Ad-Hoc Wireless Networks
73. Ho-lun Cheng, Chao Chen: Superimposing Voronoi Complexes for Shape
Deformation
74. Jinsong Tan, Louxin Zhang: Approximation Algorithms for the
Consecutive Ones Submatrix Problem on Sparse Matrices
75. Amalia Duch: Randomized Insertion and Deletion in Point Quad Trees
76. Veli Makinen, Gonzalo Navarro, Kunihiko Sadakane: Advantages of
Backward Searching - Efficient Secondary Memory and Distributed
Implementation of Compressed Suffix Arrays

I hope to see you in Hong Kong, Dec 20-22.
Rudolf Fleischer, PC chair



-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.