Algorithms and computation. 15th international symposium, ISAAC 2004, Hong Kong, China, December 20--22, 2004. Proceedings. (Q2488059)

The articles of this volume will be reviewed individually. The preceding symposium has been reviewed (see Zbl 1029.00053) Indexed articles: \textit{Demaine, Erik D.}, Puzzles, art, and magic with algorithms, 1 [Zbl 1116.68688] \textit{Mount, David M.}, The ABCs of AVDs: Geometric retrieval made simple, 2 [Zbl 1116.68639] \textit{Abraham, David J.; Cechlárová, Katarína; Manlove, David F.; Mehlhorn, Kurt}, Pareto optimality in house allocation problems, 3-15 [Zbl 1116.90393] \textit{Ailon, Nir; Chazelle, Bernard; Comandur, Seshadhri; Liu, Ding}, Property-preserving data reconstruction, 16-27 [Zbl 1116.68442] \textit{Amano, Kazuyuki; Maruoka, Akira}, On the monotone circuit complexity of quadratic Boolean functions, 28-40 [Zbl 1116.68469] \textit{Amir, Amihood; Nor, Igor}, Generalized function matching, 41-52 [Zbl 1116.68666] \textit{Andersson, Mattias; Gudmundsson, Joachim; Levcopoulos, Christos}, Approximate distance oracles for graphs with dense clusters, 53-64 [Zbl 1116.68401] \textit{Armon, Amitai; Zwick, Uri}, Multicriteria global minimum cuts, 65-76 [Zbl 1116.68545] \textit{Aronov, Boris; Asano, Tetsuo; Katoh, Naoki; Mehlhorn, Kurt; Tokuyama, Takeshi}, Polyline fitting of planar points under min-sum criteria, 77-88 [Zbl 1116.65310] \textit{Aronov, Boris; Asano, Tetsuo; Kikuchi, Yosuke; Nandy, Subhas C.; Sasahara, Shinji; Uno, Takeaki}, A generalization of magic squares with applications to digital halftoning, 89-100 [Zbl 1116.05302] \textit{Bae, Sang Won; Chwa, Kyung-Yong}, Voronoi diagrams with a transportation network on the Euclidean plane, 101-112 [Zbl 1116.90309] \textit{Bauer, Markus; Klau, Gunnar W.}, Structural alignment of two RNA sequences with Lagrangian relaxation, 113-123 [Zbl 1116.92319] \textit{Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis Th.}, Poly-APX- and PTAS-completeness in standard and differential approximation (Extended abstract), 124-136 [Zbl 1116.68678] \textit{Bengtsson, Fredrik; Chen, Jingsen}, Efficient algorithms for \(k\) maximum sums, 137-148 [Zbl 1100.68643] \textit{Bereg, Sergey}, Equipartitions of measures by 2-fans, 149-158 [Zbl 1116.68615] \textit{Bilò, Davide; Proietti, Guido}, Augmenting the edge-connectivity of a spider tree, 159-171 [Zbl 1116.05316] \textit{Bilò, Vittorio; Flammini, Michele; Melideo, Giovanna; Moscardelli, Luca}, On Nash equilibria for multicast transmissions in ad-hoc wireless networks, 172-183 [Zbl 1116.68320] \textit{Brandes, Ulrik; Lerner, Jürgen}, Structural similarity in graphs. A relaxation approach for role assignment, 184-195 [Zbl 1116.05313] \textit{Brazil, Marcus; Winter, Pawel; Zachariasen, Martin}, Flexibility of Steiner trees in uniform orientation metrics, 196-208 [Zbl 1116.68656] \textit{Cai, Jin-Yi; Watanabe, Osamu}, Random access to advice strings and collapsing results, 209-220 [Zbl 1116.68445] \textit{Calinescu, Gruia}, Bounding the payment of approximate truthful mechanisms, 221-233 [Zbl 1116.68679] \textit{Calinescu, Gruia; Zelikovsky, Alexander}, The polymatroid Steiner problems, 234-245 [Zbl 1116.68547] \textit{Chan, Timothy M.; Sadjad, Bashir S.}, Geometric optimization problems over sliding windows, 246-258 [Zbl 1116.68667] \textit{Chan, Wun-Tat; Wong, Prudence W. H.}, On-line windows scheduling of temporary items, 259-270 [Zbl 1116.68366] \textit{Chen, Danny Z.; Hu, Xiaobo S.; Luan, Shuang; Naqvi, Shahid A.; Wang, Chao; Yu, Cedric X.}, Generalized geometric approaches for leaf sequencing problems in radiation therapy, 271-281 [Zbl 1116.68617] \textit{Chen, Hsin-Fu; Chang, Maw-Shang}, An efficient exact algorithm for the minimum ultrametric tree problem, 282-293 [Zbl 1116.68668] \textit{Chen, Kuan-Yu; Chao, Kun-Mao}, On the range maximum-sum segment query problem, 294-305 [Zbl 1116.68669] \textit{Chen, Xujin; Zang, Wenan}, An efficient algorithm for finding maximum cycle packings in reducible flow graphs, 306-317 [Zbl 1116.68549] \textit{Chen, Zhenming; Singh, Vikas; Xu, Jinhui}, Efficient job scheduling algorithms with multi-type contentions, 318-329 [Zbl 1116.90345] \textit{Chen, Chao; Cheng, Ho-Lun}, Superimposing Voronoi complexes for shape deformation, 330-341 [Zbl 1116.68616] \textit{Cheng, Qi; Huang, Ming-Deh}, On partial lifting and the elliptic curve discrete logarithm problem, 342-351 [Zbl 1116.94313] \textit{Chwa, Kyung-Yong; Jo, Byung-Cheol; Knauer, Christian; Moet, Esther; van Oostrum, René; Shin, Chan-Su}, Guarding art galleries by guarding witnesses (Extended abstract), 352-363 [Zbl 1116.68618] \textit{Dai, H. K.; Su, H. C.}, On \(p\)-norm based locality measures of space-filling curves, 364-376 [Zbl 1116.68621] \textit{Dang, Zhe; Ibarra, Oscar H.; Su, Jianwen}, Composability of infinite-state activity automata, 377-388 [Zbl 1116.68488] \textit{Dom, Michael; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf}, Error compensation in leaf root problems, 389-401 [Zbl 1116.68551] \textit{Dragan, Feodor F.; Lomonosov, Irina}, On compact and efficient routing in certain graph classes (Extended abstract), 402-414 [Zbl 1116.68552] \textit{Duch, Amalia}, Randomized insertion and deletion in point quad trees, 415-426 [Zbl 1116.68402] \textit{Fu, Bin; Beigel, Richard}, Diagnosis in the presence of intermittent faults, 427-441 [Zbl 1116.68364] \textit{Fujita, Satoshi; Araki, Toru}, Three-round adaptive diagnosis in binary \(n\)-cubes, 442-451 [Zbl 1116.68365] \textit{Fukagawa, Daiji; Akutsu, Tatsuya}, Fast algorithms for comparison of similar unordered trees, 452-463 [Zbl 1116.68554] \textit{von zur Gathen, Joachim; Shparlinski, Igor E.}, GCD of random linear forms, 464-469 [Zbl 1116.68687] \textit{Goerdt, Andreas; Lanka, André}, On the hardness and easiness of random 4-SAT formulas, 470-483 [Zbl 1116.68471] \textit{Goldstein, Avraham; Kolman, Petr; Zheng, Jie}, Minimum common string partition problem: Hardness and approximations, 484-495 [Zbl 1116.68472] \textit{Goldstein, Darin; Kobayashi, Kojiro}, On the complexity of network synchronization, 496-507 [Zbl 1116.68473] \textit{Golin, Mordecai J.; Leung, Yiu Cho; Wang, Yajun}, Counting spanning trees and other structures in non-constant-jump circulant graphs (Extended abstract), 508-521 [Zbl 1116.05303] \textit{Hershberger, John; Shrivastava, Nisheeth; Suri, Subhash; Tóth, Csaba D.}, Adaptive spatial partitioning for multidimensional data streams, 522-533 [Zbl 1116.68403] \textit{Hui, Peter; Schaefer, Marcus}, Paired pointset traversal, 534-544 [Zbl 1116.68628] \textit{Iwama, Kazuo; Kawachi, Akinori}, Approximated two choices in randomized load balancing, 545-557 [Zbl 1116.68369] \textit{JaJa, Joseph; Mortensen, Christian W.; Shi, Qingmin}, Space-efficient and fast algorithms for multidimensional dominance reporting and counting, 558-568 [Zbl 1116.68629] \textit{Jansson, Jesper; Hieu, Ngo Trung; Sung, Wing-Kin}, Local gapped subforest alignment and its application in finding RNA structural motifs, 569-580 [Zbl 1116.68670] \textit{Jansson, Jesper; Sung, Wing-Kin}, The maximum agreement of two nested phylogenetic networks, 581-593 [Zbl 1116.68671] \textit{Jaromczyk, Jerzy W.; Lonc, Zbigniew}, Sequences of radius \(k\): how to fetch many huge objects into small memory for pairwise computations, 594-605 [Zbl 1116.68544] \textit{Jiang, Minghui; Bereg, Sergey; Qin, Zhongping; Zhu, Binhai}, New bounds on map labeling with circular labels, 606-617 [Zbl 1116.68680] \textit{Kim, Jae-Hoon}, Optimal buffer management via resource augmentation, 618-628 [Zbl 1116.68370] \textit{Wanke, Egon; Kötter, Rolf}, Oriented paths in mixed graphs, 629-643 [Zbl 1116.68563] \textit{Kowalski, Dariusz R.; Pelc, Andrzej}, Polynomial deterministic rendezvous in arbitrary graphs, 644-656 [Zbl 1116.68556] \textit{Lefmann, Hanno}, Distributions of points and large quadrangles (Extended abstract), 657-668 [Zbl 1116.68634] \textit{Daescu, Ovidiu; Luo, Jun}, Cutting out polygons with lines and rays, 669-680 [Zbl 1116.68620] \textit{Mäkinen, Veli; Navarro, Gonzalo; Sadakane, Kunihiko}, Advantages of backward searching -- efficient secondary memory and distributed implementation of compressed suffix arrays, 681-692 [Zbl 1116.68408] \textit{Miura, Kazuyuki; Haga, Hiroki; Nishizeki, Takao}, Inner rectangular drawings of plane graphs (Extended abstract), 693-704 [Zbl 1116.68638] \textit{Nagamochi, Hiroshi; Kawada, Taizo}, Approximating the minmax subtree cover problem in a cactus, 705-716 [Zbl 1116.68558] \textit{Nowakowski, Richard J.; Zeh, Norbert}, Boundary-optimal triangulation flooding, 717-728 [Zbl 1116.68642] \textit{von Oertzen, Timo}, Exact computation of polynomial zeros expressible by square roots, 729-741 [Zbl 1116.68686] \textit{Park, Jung-Heum; Kim, Hee-Chul; Lim, Hyeong-Seok}, Many-to-many disjoint path covers in a graph with faulty elements, 742-753 [Zbl 1116.68559] \textit{Peng, Zeshan; Ting, Hingfung}, An \(O(n\log n)\)-time algorithm for the maximum constrained agreement subtree problem for binary trees, 754-765 [Zbl 1116.68672] \textit{Pessoa, Artur Alves}, Planning the transportation of multiple commodities in bidirectional pipeline networks, 766-777 [Zbl 1116.90316] \textit{Pessoa, Artur Alves; Laber, Eduardo Sany; de Souza, Críston}, Efficient algorithms for the hotlink assignment problem: The worst case search, 778-792 [Zbl 1116.68681] \textit{Raitner, Marcus}, Dynamic tree cross products, 793-804 [Zbl 1116.68405] \textit{Schindelhauer, Christian; Volbert, Klaus; Ziegler, Martin}, Spanners, weak spanners, and power spanners for wireless networks, 805-821 [Zbl 1116.68561] \textit{Shi, Qingmin; JaJa, Joseph}, Techniques for indexing and querying temporal observations for a collection of objects, 822-834 [Zbl 1116.68412] \textit{Tan, Jinsong; Zhang, Louxin}, Approximation algorithms for the consecutive ones submatrix problem on sparse matrices, 835-846 [Zbl 1116.68682] \textit{Tan, Xuehou}, The two-guard problem revisited and its generalization, 847-858 [Zbl 1116.68650] \textit{Uehara, Ryuhei}, Canonical data structure for interval probe graphs, 859-870 [Zbl 1116.68406] \textit{Uehara, Ryuhei; Uno, Yushi}, Efficient algorithms for the longest path problem, 871-883 [Zbl 1116.05318] \textit{Wang, Lusheng; Dong, Liang; Fan, Hui}, Randomized algorithms for motif detection, 884-895 [Zbl 1116.68676] \textit{de Werra, Dominique; Demange, Mare; Escoffier, Bruno; Monnot, Jerome; Paschos, Vangelis Th.}, Weighted coloring on planar, bipartite and split graphs: Complexity and improved approximation, 896-907 [Zbl 1116.68565] \textit{Yang, Boting; Dyer, Danny; Alspach, Brian}, Sweeping graphs with large clique number (Extended abstract), 908-920 [Zbl 1116.05314] \textit{Zwick, Uri}, A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths, 921-932 [Zbl 1116.68564]