14. ISAAC 2003: Kyoto, Japan

Invited Talks

• Andrew Chi-Chih Yao:
  Interactive Proofs for Quantum Computation. 1
  
• Takao Nishizeki:
  Drawing Plane Graphs. 2-5
  

Computational Complexity I

• Jinhee Chun, Kunihiko Sadakane, Takeshi Tokuyama:
  Linear Time Algorithm for Approximating a Curve by a Single-Peaked Curve. 6-15
  
• Anil Maheshwari, Michiel H. M. Smid:
  A Dynamic Dictionary for Priced Information with Application. 16-25
  
• Tetsushi Nishida, Kokichi Sugihara:
  Voronoi Diagram in the Flow Field. 26-35
  
• Ovidiu Daescu, Ningfang Mi:
  Polygonal Path Approximation: A Query Based Approach. 36-46
  

Graph and Combinatorial Algorithms I

• Anne Berry, Pinar Heggernes, Yngve Villanger:
  A Vertex Incremental Approach for Dynamically Maintaining Chordal Graphs. 47-57
  
• Atsuko Yamaguchi, Hiroshi Mamitsuka:
  Finding the Maximum Common Subgraph of a Partial k-Tree and a Graph with a Polynomially Bounded Number of Spanning Trees. 58-67
  
• Ornan Ori Gerstel, Shay Kutten, Rachel Matichin, David Peleg:
  Hotlink Enhancement Algorithms for Web Directories: (Extended Abstract). 68-77
  
• Rung-Ren Lin, Wen-Hsiung Kuo, Kun-Mao Chao:
  Finding a Length-Constrained Maximum-Density Path in a Tree. 78-87
  

Computational Complexity II

• Bodo Manthey, Rüdiger Reischuk:
  The Intractability of Computing the Hamming Distance. 88-97
  
• Richard Beigel, Lance Fortnow, Frank Stephan:
  Infinitely-Often Autoreducible Sets. 98-107
  
• Shao Chin Sung, Keisuke Tanaka:
  Limiting Negations in Bounded-Depth Circuits: An Extension of Markov's Theorem. 108-116
  
• Tomoyuki Yamakami:
  Computational Complexity Measures of Multipartite Quantum Entanglement. 117-128
  

Graph and Combinatorial Algorithms II

• Gabriel Valiente:
  A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs. 129-137
  
• Hiroshi Nagamochi, Kohei Okada:
  Polynomial Time 2-Approximation Algorithms for the Minmax Subtree Cover Problem. 138-147
  
• Jianer Chen, Iyad A. Kanj, Ge Xia:
  Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems. 148-157
  
• Hiroaki Yamamoto:
  A New Translation from Semi-extended Regular Expressions into NFAs and Its Application to an Approximate Matching Problem. 158-167
  

Quantum Computation

• Vikraman Arvind, Rainer Schuler:
  The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems. 168-177
  
• Hirotada Kobayashi:
  Non-interactive Quantum Perfect and Statistical Zero-Knowledge. 178-188
  
• Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami:
  Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur? 189-198
  
• Christoph Ludwig:
  A Faster Lattice Reduction Method Using Quantum Search. 199-208
  

Graph and Combinatorial Algorithms III

• Amr Elmasry:
  Three Sorting Algorithms Using Priority Queues. 209-220
  
• Grzegorz Stachowiak:
  Lower Bounds on Correction Networks. 221-229
  
• Gonzalo Navarro:
  Approximate Regular Expression Searching with Arbitrary Integer Weights. 230-239
  
• Wing-Kai Hon, Tak Wah Lam, Kunihiko Sadakane, Wing-Kin Sung:
  Constructing Compressed Suffix Arrays with Large Alphabets. 240-249
  

Computational Geometry II

• Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein:
  On the Geometric Dilation of Finite Point Sets. 250-259
  
• Jae-Sook Cheong, Herman J. Haverkort, A. Frank van der Stappen:
  On Computing All Immobilizing Grasps of a Simple Polygon with Few Contacts. 260-269
  
• José Miguel Díaz-Báñez, Ferran Hurtado, Mario Alberto López, Joan Antoni Sellarès:
  Optimal Point Set Projections onto Regular Grids. 270-279
  

Combinatorial Optimization I

• Hiroshi Nagamochi, Yuusuke Abe:
  An Approximation Algorithm for Dissecting a Rectangle into Rectangles with Specified Areas. 280-289
  
• Friedrich Eisenbrand, Sören Laue:
  A Faster Algorithm for Two-Variable Integer Programming. 290-299
  
• Adrian Dumitrescu:
  Efficient Algorithms for Generation of Combinatorial Covering Suites. 300-308
  

Scheduling

• Yoshiyuki Karuno, Hiroshi Nagamochi:
  A Better Approximation for the Two-Machine Flowshop Scheduling Problem with Time Lags. 309-318
  
• Aleksei V. Fishkin, Klaus Jansen, Monaldo Mastrolilli:
  On Minimizing Average Weighted Completion Time: A PTAS for the Job Shop Problem with Release Dates. 319-328
  
• Deshi Ye, Guochuan Zhang:
  Online Scheduling of Parallel Jobs with Dependencies on 2-Dimensional Meshes. 329-338
  

Computational Biology

• Yaw-Ling Lin, Tsan-sheng Hsu:
  Efficient Algorithms for Descendent Subtrees Comparison of Phylogenetic Trees with Applications to Co-evolutionary Classifications in Bacterial Genome. 339-351
  
• Isaac Elias:
  Settling the Intractability of Multiple Alignment. 352-363
  
• Tak Wah Lam, N. Lu, Hing-Fung Ting, Prudence W. H. Wong, Siu-Ming Yiu:
  Efficient Algorithms for Optimizing Whole Genome Alignment with Noise. 364-374
  

Computational Geometry III

• Xiaodong Wu:
  Segmenting Doughnut-Shaped Objects in Medical Images. 375-384
  
• Ho-Kwok Dai, Hung-Chi Su:
  On the Locality Properties of Space-Filling Curves. 385-394
  
• Erik D. Demaine, Stefan Langerman, Joseph O'Rourke:
  Geometric Restrictions on Producible Polygonal Protein Chains. 395-404
  
• Seok-Hee Hong, Peter Eades:
  Symmetric Layout of Disconnected Graphs. 405-414
  

Graph and Computational Algorithms IV

• Miroslav Chlebík, Janka Chlebíková:
  Approximation Hardness of Minimum Edge Dominating Set and Minimum Maximal Matching. 415-424
  
• Nadia Takki-Chebihi, Takeshi Tokuyama:
  Enumerating Global Roundings of an Outerplanar Graph. 425-433
  
• Toshimasa Ishii, Shigeyuki Yamamoto, Hiroshi Nagamochi:
  Augmenting Forests to Meet Odd Diameter Requirements. 434-443
  
• Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten:
  On the Existence and Determination of Satisfactory Partitions in a Graph. 444-453
  

Distributed and Parallel Algorithms

• Tom Altman, Yoshihide Igarashi, Michiko Omori:
  A Turn Function Scheme Realized in the Asynchronous Single-Writer/Multi-reader Shared Memory Model. 454-463
  
• Abul Kashem, M. Ziaur Rahman:
  An Optimal Parallel Algorithm for c-Vertex-Ranking of Trees. 464-473
  

Graph and Computational Algorithms V

• David J. Abraham, Robert W. Irving, David Manlove:
  The Student-Project Allocation Problem. 474-484
  
• Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan:
  Algorithms for Enumerating Circuits in Matroids. 485-494
  
• Akinobu Eguchi, Satoru Fujishige, Akihisa Tamura:
  A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Model. 495-504
  

Data Structure

• Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung:
  Succinct Data Structures for Searchable Partial Sums. 505-516
  
• Danny Krizanc, Pat Morin, Michiel H. M. Smid:
  Range Mode and Range Median Queries on Lists and Trees. 517-526
  
• Ferdinando Cicalese, Christian Deppe:
  Quasi-Perfect Minimally Adaptive q-ary Search with Unreliable Tests. 527-536
  
• Travis Gagie:
  New Ways to Construct Binary Search Trees. 537-543
  

Graph and Computational Algorithms VI

• Artur Czumaj, Andrzej Lingas, Johan Nilsson:
  Improved Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth. 544-553
  
• Raffaella Gentilini, Alberto Policriti:
  Biconnectivity on Symbolically Represented Graphs: A Linear Solution. 554-564
  
• Torsten Tholey:
  A Dynamic Data Structure for Maintaining Disjoint Paths Information in Digraphs. 565-574
  
• Jérémy Barbay, Claire Kenyon:
  Deterministic Algorithm for the t-Threshold Set Problem. 575-584
  

Combinatorical and Network Optimization

• Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos:
  Energy-Efficient Wireless Network Design. 585-594
  
• Thomas Erlebach, Stamatis Stefanakos:
  Wavelength Conversion in Shortest-Path All-Optical Networks. 595-604
  
• Amin Coja-Oghlan, Sven Oliver Krumke, Till Nierhoff:
  A Heuristic for the Stacker Crane Problem on Trees Which Is Almost Surely Exact. 605-614
  
• Stephan Eidenbenz, Aris Pagourtzis, Peter Widmayer:
  Flexible Train Rostering. 615-624
  

Computational Complexity and Cryptography

• Peter Bürgisser, Felipe Cucker:
  Counting Complexity Classes over the Reals I: The Additive Case. 625-634
  
• Atsuyuki Inoue, Akira Ito, Katsushi Inoue, Tokio Okazaki:
  Some Properties of One-Pebble Turing Machines with Sublogarithmic Space. 635-644
  
• Giovanni Di Crescenzo, Clemente Galdi:
  Hypergraph Decomposition and Secret Sharing. 645-654
  
• Eun-Kyung Ryu, Kee-Won Kim, Kee-Young Yoo:
  A Promising Key Agreement Protocol. 655-662
  

Game Theory and Ramdonized Algorithms

• Ravi Kannan, Michael W. Mahoney, Ravi Montenegro:
  Rapid Mixing of Several Markov Chains for a Hard-Core Model. 663-675
  
• Tomomi Matsui, Mitsuo Motoki, Naoyuki Kamatani:
  Polynomial Time Approximate Sampler for Discretized Dirichlet Distribution. 676-685
  
• Yoshio Okamoto:
  Fair Cost Allocations under Conflicts - A Game-Theoretic Point of View. 686-695
  
• George Karakostas, Anastasios Viglas:
  Equilibria for Networks with Malicious Users. 696-704
  

Algebraic and Arithmetic Computation

• Martin Ziegler:
  Quasi-optimal Arithmetic for Quaternion Polynomials. 705-715
  
• Vikraman Arvind, Piyush P. Kurur:
  Upper Bounds on the Complexity of Some Galois Theory Problems. 716-725
  
• Wieland Fischer, Jean-Pierre Seifert:
  Unfolded Modular Multiplication. 726-735
  
• Soonhak Kwon, Chang Hoon Kim, Chun Pyo Hong:
  Gauss Period, Sparse Polynomial, Redundant Basis, and Efficient Exponentiation for a Class of Finite Fields with Small Characteristic. 736-745