Algorithms and computation. 14th international symposium, ISAAC 2003, Kyoto, Japan, December 15--17, 2003. Proceedings (Q1418348)

The articles of this volume will be reviewed individually. The preceding symposium has been reviewed (see Zbl 1007.00050). Indexed articles: \textit{Nishizeki, Takao}, Drawing plane graphs, 2-5 [Zbl 1205.68267] \textit{Chun, Jinhee; Sadakane, Kunihiko; Tokuyama, Takeshi}, Linear time algorithm for approximating a curve by a single-peaked curve, 6-15 [Zbl 1205.68459] \textit{Maheshwari, Anil; Smid, Michiel}, A dynamic dictionary for priced information with application, 16-25 [Zbl 1205.68131] \textit{Nishida, Tetsushi; Sugihara, Kokichi}, Voronoi diagram in the flow field, 26-35 [Zbl 1205.68469] \textit{Daescu, Ovidiu; Mi, Ningfang}, Polygonal path approximation: a query based approach, 36-46 [Zbl 1205.68461] \textit{Berry, Anne; Heggernes, Pinar; Villanger, Yngve}, A vertex incremental approach for dynamically maintaining chordal graphs, 47-57 [Zbl 1205.68256] \textit{Yamaguchi, Atsuko; Mamitsuka, Hiroshi}, Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees, 58-67 [Zbl 1205.68270] \textit{Gerstel, Ori; Kutten, Shay; Matichin, Rachel; Peleg, David}, Hotlink enhancement algorithms for web directories, 68-77 [Zbl 1205.68070] \textit{Lin, Rung-Ren; Kuo, Wen-Hsiung; Chao, Kun-Mao}, Finding a length-constrained maximum-density path in a tree, 78-87 [Zbl 1205.68265] \textit{Manthey, Bodo; Reischuk, Rüdiger}, The intractability of computing the Hamming distance, 88-97 [Zbl 1205.68173] \textit{Beigel, Richard; Fortnow, Lance; Stephan, Frank}, Infinitely-often autoreducible sets, 98-107 [Zbl 1205.68161] \textit{Sung, Shao Chin; Tanaka, Keisuke}, Limiting negations in bounded-depth circuits: an extension of Markov's theorem, 108-116 [Zbl 1205.68176] \textit{Yamakami, Tomoyuki}, Computational complexity measures of multipartite quantum entanglement, 117-128 [Zbl 1205.81065] \textit{Valiente, Gabriel}, A new simple algorithm for the maximum-weight independent set problem on circle graphs, 129-137 [Zbl 1205.05171] \textit{Nagamochi, Hiroshi; Okada, Kohei}, Polynomial time 2-approximation algorithms for the minmax subtree cover problem, 138-147 [Zbl 1205.68518] \textit{Chen, Jianer; Kanj, Iyad A.; Xia, Ge}, Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems, 148-157 [Zbl 1205.68530] \textit{Yamamoto, Hiroaki}, A new translation from semi-extended regular expressions into NFAs and its application to an approximate matching problem, 158-167 [Zbl 1205.68214] \textit{Arvind, V.; Schuler, Rainer}, The quantum query complexity of 0-1 knapsack and associated claw problems, 168-177 [Zbl 1205.68157] \textit{Kobayashi, Hirotada}, Non-interactive quantum perfect and statistical zero-knowledge, 178-188 [Zbl 1205.68158] \textit{Kobayashi, Hirotada; Matsumoto, Keiji; Yamakami, Tomoyuki}, Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?, 189-198 [Zbl 1205.68159] \textit{Ludwig, Christoph}, A faster lattice reduction method using quantum search, 199-208 [Zbl 1205.68160] \textit{Elmasry, Amr}, Three sorting algorithms using priority queues, 209-220 [Zbl 1205.68135] \textit{Stachowiak, Grzegorz}, Lower bounds on correction networks, 221-229 [Zbl 1205.68138] \textit{Navarro, Gonzalo}, Approximate regular expression searching with arbitrary integer weights, 230-239 [Zbl 1205.68527] \textit{Hon, Wing-Kai; Lam, Tak-Wah; Sadakane, Kunihiko; Sung, Wing-Kin}, Constructing compressed suffix arrays with large alphabets, 240-249 [Zbl 1205.68128] \textit{Ebbers-Baumann, Annette; Grüne, Ansgar; Klein, Rolf}, On the geometric dilation of finite point sets, 250-259 [Zbl 1205.68463] \textit{Cheong, Jae-Sook; Haverkort, Herman J.; van der Stappen, A. Frank}, On computing all immobilizing grasps of a simple polygon with few contacts, 260-269 [Zbl 1205.68458] \textit{Díaz-Báñez, José Miguel; Hurtado, Ferran; López, Mario Alberto; Sellarès, J. Antoni}, Optimal point set projections onto regular grids, 270-279 [Zbl 1205.68462] \textit{Nagamochi, Hiroshi; Abe, Yuusuke}, An approximation algorithm for dissecting a rectangle into rectangles with specified areas, 280-289 [Zbl 1205.68517] \textit{Eisenbrand, Friedrich; Laue, Sören}, A faster algorithm for two-variable integer programming, 290-299 [Zbl 1205.90198] \textit{Dumitrescu, Adrian}, Efficient algorithms for generation of combinatorial covering suites, 300-308 [Zbl 1205.68122] \textit{Karuno, Yoshiyuki; Nagamochi, Hiroshi}, A better approximation for the two-machine flowshop scheduling problem with time lags, 309-318 [Zbl 1205.90125] \textit{Fishkin, Aleksei V.; Jansen, Klaus; Mastrolilli, Monaldo}, On minimizing average weighted completion time: A PTAS for the job shop problem with release dates, 319-328 [Zbl 1205.90122] \textit{Ye, Deshi; Zhang, Guochuan}, Online scheduling of parallel jobs with dependencies on 2-dimensional meshes, 329-338 [Zbl 1205.68105] \textit{Lin, Yaw-Ling; Hsu, Tsan-Sheng}, Efficient algorithms for descendent subtrees comparison of phylogenetic trees with applications to co-evolutionary classifications in bacterial genome, 339-351 [Zbl 1205.92055] \textit{Elias, Isaac}, Settling the intractability of multiple alignment, 352-363 [Zbl 1205.68171] \textit{Lam, T. W.; Lu, N.; Ting, H. F.; Wong, Prudence W. H.; Yiu, S. M.}, Efficient algorithms for optimizing whole genome alignment with noise, 364-374 [Zbl 1205.92021] \textit{Wu, Xiaodong}, Segmenting doughnut-shaped objects in medical images, 375-384 [Zbl 1205.92043] \textit{Dai, H. K.; Su, H. C.}, On the locality properties of space-filling curves, 385-394 [Zbl 1205.68476] \textit{Demaine, Erik D.; Langerman, Stefan; O'Rourke, Joseph}, Geometric restrictions on producible polygonal protein chains, 395-404 [Zbl 1205.92020] \textit{Hong, Seok-Hee; Eades, Peter}, Symmetric layout of disconnected graphs, 405-414 [Zbl 1205.68467] \textit{Chlebík, Miroslav; Chlebíková, Janka}, Approximation hardness of minimum edge dominating set and minimum maximal matching, 415-424 [Zbl 1205.68168] \textit{Takki-Chebihi, Nadia; Tokuyama, Takeshi}, Enumerating global roundings of an outerplanar graph, 425-433 [Zbl 1205.05109] \textit{Ishii, Toshimasa; Yamamoto, Shigeyuki; Nagamochi, Hiroshi}, Augmenting forests to meet odd diameter requirements, 434-443 [Zbl 1205.05224] \textit{Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel}, On the existence and determination of satisfactory partitions in a graph, 444-453 [Zbl 1205.68255] \textit{Altman, Tom; Igarashi, Yoshihide; Omori, Michiko}, A turn function scheme realized in the asynchronous single-writer/multi-reader shared memory model, 454-463 [Zbl 1205.68083] \textit{Kashem, Md. Abul; Rahman, M. Ziaur}, An optimal parallel algorithm for \(c\)-vertex-ranking of trees, 464-473 [Zbl 1205.68500] \textit{Abraham, David J.; Irving, Robert W.; Manlove, David F.}, The student-project allocation problem, 474-484 [Zbl 1205.05236] \textit{Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir; Khachiyan, Leonid}, Algorithms for enumerating circuits in matroids, 485-494 [Zbl 1205.05038] \textit{Eguchi, Akinobu; Fujishige, Satoru; Tamura, Akihisa}, A generalized Gale-Shapley algorithm for a discrete-concave stable-marriage model, 495-504 [Zbl 1205.05237] \textit{Hon, Wing-Kai; Sadakane, Kunihiko; Sung, Wing-Kin}, Succinct data structures for searchable partial sums, 505-516 [Zbl 1205.68129] \textit{Krizanc, Danny; Morin, Pat; Smid, Michiel}, Range mode and range median queries on lists and trees, 517-526 [Zbl 1205.68130] \textit{Cicalese, Ferdinando; Deppe, Christian}, Quasi-perfect minimally adaptive \(q\)-ary search with unreliable tests, 527-536 [Zbl 1205.68371] \textit{Gagie, Travis}, New ways to construct binary search trees, 537-543 [Zbl 1205.68126] \textit{Czumaj, Artur; Lingas, Andrzej; Nilsson, Johan}, Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth, 544-553 [Zbl 1205.68511] \textit{Gentilini, Raffaella; Policriti, Alberto}, Biconnectivity on symbolically represented graphs: A linear solution, 554-564 [Zbl 1205.05220] \textit{Tholey, Torsten}, A dynamic data structure for maintaining disjoint paths information in digraphs, 565-574 [Zbl 1205.68133] \textit{Barbay, Jérémy; Kenyon, Claire}, Deterministic algorithm for the \(t\)-threshold set problem, 575-584 [Zbl 1205.68492] \textit{Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis}, Energy-efficient wireless network design, 585-594 [Zbl 1205.68027] \textit{Erlebach, Thomas; Stefanakos, Stamatis}, Wavelength conversion in shortest-path all-optical networks, 595-604 [Zbl 1205.68032] \textit{Coja-Oghlan, Amin; Krumke, Sven O.; Nierhoff, Till}, A heuristic for the stacker crane problem on trees which is almost surely exact, 605-614 [Zbl 1205.90287] \textit{Eidenbenz, Stephan; Pagourtzis, Aris; Widmayer, Peter}, Flexible train rostering, 615-624 [Zbl 1205.90120] \textit{Bürgisser, Peter; Cucker, Felipe}, Counting complexity classes over the reals. I: The additive case, 625-634 [Zbl 1205.68162] \textit{Inoue, Atsuyuki; Ito, Akira; Inoue, Katsushi; Okazaki, Tokio}, Some properties of one-pebble Turing machines with sublogarithmic space, 635-644 [Zbl 1205.68153] \textit{Di Crescenzo, Giovanni; Galdi, Clemente}, Hypergraph decomposition and secret sharing, 645-654 [Zbl 1205.94106] \textit{Ryu, Eun-Kyung; Kim, Kee-Won; Yoo, Kee-Young}, A promising key agreement protocol, 655-662 [Zbl 1205.94109] \textit{Kannan, Ravi; Mahoney, Michael W.; Montenegro, Ravi}, Rapid mixing of several Markov chains for a hard-core model, 663-675 [Zbl 1205.60137] \textit{Matsui, Tomomi; Motoki, Mitsuo; Kamatani, Naoyuki}, Polynomial time approximate sampler for discretized Dirichlet distribution, 676-685 [Zbl 1205.62122] \textit{Okamoto, Yoshio}, Fair cost allocations under conflicts -- a game-theoretic point of view, 686-695 [Zbl 1205.91098] \textit{Karakostas, George; Viglas, Anastasios}, Equilibria for networks with malicious users, 696-704 [Zbl 1205.68039] \textit{Ziegler, Martin}, Quasi-optimal arithmetic for quaternion polynomials, 705-715 [Zbl 1205.68522] \textit{Arvind, V.; Kurur, Piyush P.}, Upper bounds on the complexity of some Galois theory problems, 716-725 [Zbl 1205.11137] \textit{Fischer, Wieland; Seifert, Jean-Pierre}, Unfolded modular multiplication, 726-735 [Zbl 1205.94082] \textit{Kwon, Soonhak; Kim, Chang Hoon; Hong, Chun Pyo}, Gauss period, sparse polynomial, redundant basis, and efficient exponentiation for a class of finite fields with small characteristic, 736-745 [Zbl 1205.12007]