ISAAC 2002
Accepted Papers
On the minimum volume of a perturbed unit cube
Jin-Yi Cai, University of Wisconsin, Madison
A Simple New Approach to Curve Reconstruction
Sumanta Guha, University of Wisconsin-Milwaukee
Paula Josiah, University of Wisconsin-Milwaukee
Anoop Mittal, University of Wisconsin-Milwaukee
Son Dinh Tran, University of Wisconsin-Milwaukee
On the Comparison-Addition Complexity of All-Pairs Shortest Paths
Seth Pettie, The University of Texas at Austin
On the clique-width of graphs in hereditary classes
Rodica Boliac, RUTCOR, Rutgers Center for Operations Research, Rutgers University
Vadim Lozin, RUTCOR, Rutgers Center for Operations Research, Rutgers University
An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering
Klaus Jansen, Universtaet zu Kiel
Roberto Solis-Oba, University of Western Ontario
Project scheduling with irregular costs: Complexity, approximability, and algorithms
Alexander Grigoriev, University of Maastricht
Gerhard Woeginger, University of Twente
Crossing Minimization for Symmetries
Christoph Buchheim, University of Cologne
Seok-Hee Hong, University of Sydney
On the Emptiness Problem for Two-Way NFA with One Reversal-Bounded Counter
Zhe Dang, School of EECS, Washington State University
Oscar Ibarra, Department of Computer Science, University of California at Santa Barbara
Zhi-wei Sun, Department of Mathematics, Nanjing University
File Transfer Tree Problems
Hiro Ito, Kyoto University
Hiroshi Nagamochi, Toyohashi University of Technology
Yosuke Sugiyama, Internet Ware Corporation
Masao Fujita, Fujitsu Kansai-Chubu Net-Tech Limited
The probability of a rendezvous is minimal in complete graphs
Martin Dietzfelbinger, Technische Universitaet Ilmenau
Cutting a Country for Smallest Square Fit
Marc van Kreveld, Institute for Information and Computing Sciences, Utrecht University
Bettina Speckmann, Institute for Theoretical Computer Science, ETH Zürich
Meaningful Information
Paul Vitanyi, CWI and University of Amsterdam
Optimal Clearing of Supply/Demand Curves
Tuomas Sandholm, CMU
Subhash Suri, UCSB
A better approximation for the two-stage assembly scheduling problem with two machines at the first stage
Yoshiyuki Karuno, Kyoto Institute of Technology
Hiroshi Nagamochi, Toyohashi University of Technology
Casting a Polyhedron with Directional Uncertainty
Hee-Kap Ahn, Korea Institute of Science and Technology
Otfried Cheong, Utrecht University
Rene van Oostrum, Utrecht University
Approximation Algorithms for some Parameterized Counting Problems
Vikraman Arvind, Institute of Mathematical Sciences, Chennai 600 113, India
Venkatesh Raman, Institute of Mathematical Sciences, Chennai 600 113, India
Scheduling of independent dedicated multiprocessor tasks
Evripidis Bampis, Univerite d'Evry
Massimiliano Caramia, stituto per le Applicazioni del Calcolo
Antonio Iovanella, University of Rome ``Tor Vergata''
Jiri Fiala, Charles University
Aleksei V. Fishkin, Kiel University
Hierarchy of Surface Models and Irreducible Triangulation
Siu-Wing Cheng, Department of Computer Science, HKUST
Tamal Dey, Department of Computer and Information Sciences, Ohio State University
Sheung-Hung Poon, Department of Computer Science, HKUST
Average-Case Communication-Optimal Parallel Parenthesis Matching
Chun-Hsi Huang, University of Connecticut
Xin He, State University of New York at Buffalo
Algorithms and Complexity for Tetrahedralization Tedection
Boting Yang, Dept. of Computer Science, Memorial University of Newfoundland
Cao An Wang, Dept. of Computer Science, Memorial University of Newfoundland
Biased Skip Lists
Amitabha Bagchi, Johns Hopkins University
Adam Buchsbaum, AT&T Labs--Research
Michael Goodrich, University of California, Irvine
An Improved Algorithm for the Minimum Manhattan Network Problem
Ryo Kato, Chuo University
Keiko Imai, Chuo University
Takao Asano, Chuo University
Partitioning Trees of Supply and Demand
Takehiro Ito, Graduate School of Information Sciences, Tohoku University
Xiao Zhou, Graduate School of Information Sciences, Tohoku University
Takao Nishizeki, Graduate School of Information Sciences, Tohoku University
Space-Efficient Data Structures for Flexible Text Retrieval Systems
Kunihiko Sadakane, Tohoku University
Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint
Markus Blaeser, Universitaet zu Luebeck
Bodo Siebert, Universitaet zu Luebeck
A framework for network reliability problems on graphs of bounded treewidth
Thomas Wolle, Institute of Information and Computing Sciences, Utrecht University, The Netherlands
Faster Fixed Parameter Tractable Algorithms for Undirected Feedback Vertex Set
Venkatesh Raman, The Institute of Mathematical Sciences, Chennai, INDIA
Saket Saurabh, The Institute of Mathematical Sciences, Chennai, INDIA
Chinthamani, R. Subramanian, The Institute of Mathematical Sciences, Chennai, INDIA
Quantum Multi-Prover Interactive Proof Systems with Limited Prior Entanglement
Hirotada Kobayashi, Quantum Computation and Information Project, ERATO, JST
Keiji Matsumoto, Quantum Computation and Information Project, ERATO, JST
Approximate distance oracles revisited
Joachim Gudmundsson, Utrecht University, the Netherlands
Christos Levcopoulos, Lund University, Sweden
Giri Narasimhan, Florida International University, USA
Michiel Smid, Carleton University, Canada
Flat-State Connectivity of Linkages under Dihedral Motions
Greg Aloupis, McGill University
Erik D. Demaine, Massachusetts Institute of Technology
Vida Dujmovic, McGill University
Jeff Erickson, University of Illinois, Urbana-Champaign
Stefan Langerman, McGill University
Henk Meijer, Queen's University
Joseph ORourke, Smith College
Mark Overmars, Utrecht University
Michael Soss, Chemical Computing Group
Ileana Streinu, Smith College
Godfried T. Toussaint, McGill University
On the Clique Problem in Intersection Graphs of Ellipses
Christoph Ambuehl, Institute for Theoretical Computer Science, ETH Zuerich
Uli Wagner, Institute for Theoretical Computer Science, ETH Zuerich
A Faster Approximation Algorithm for 2-Edge-Connectivity Augmentation
Anna Galluccio, Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti - CNR - Roma
Guido Proietti, Dipartimento di Informatica - Universita' di L'Aquila
Optimal F-Reliable Protocols for the Do- All Problem on Single-Hop Wireless Networks
Andrea Clementi, Universita' di Roma Tor Vergata
Angelo Monti, Universita' di Roma La Sapienza
Riccardo Silvestri, Universita' di Roma La Sapienza
On the Approximability of Multiprocessor Task Scheduling Problems
Antonio Miranda, Bucknell University
Luz Torres, Bucknell University
Jianer Chen, Texas A&M University
New Results for Energy-Efficient Broacasting in Wireless Networks
Ioannis Caragiannis, CTI and University of Patras
Christos Kaklamanis, CTI and University of Patras
Panagiotis Kanellopoulos, CTI and University of Patras
Improved Distance Oracles for Avoiding Link-Failure
Rezaul Alam Chowdhury, The University of Texas at Austin, Austin, TX 78712, U.S.A.
Vijaya Ramachandran, The University of Texas at Austin, Austin, TX 78712, U.S.A.
The Wakeup Problem in Single-Hop Radio Networks
Tomasz Jurdzinski, Wroclaw University & TU Chemnitz
Grzegorz Stachowiak, Wroclaw University
Some Remarks on the L-conjecture
Qi Cheng, University of Oklahoma
Key Independent Optimality
John Iacono, Polytechnic University
Tree Spanners on Chordal Graphs: Complexity, Algorithms, Open Problems
Andreas Brandstaedt, Institut fuer Theoretische Informatik, Fachbereich Informatik, Universitaet Rostock
Feodor Dragan, Department of Computer Science, Kent State University
Hoang-Oanh Le, Institut fuer Theoretische Informatik, Fachbereich Informatik, Universitaet Rostock
Van Bang Le, Institut fuer Theoretische Informatik, Fachbereich Informatik, Universitaet Rostock
An $O(pn + 1.15^p)$-Algorithm for $p$-{\sc Profit Cover} and its Practical Implications for Vertex Cover
Ulrike Stege, University of Victoria
Iris van Rooij, University of Victoria
Alex Hertel, University of Victoria
Philipp Hertel, University of Victoria
Exponential Speedup of Fixed-Parameter Algorithms on K_{3,3}-minor-free or K_5-minor-free Graphs
Erik D. Demaine, Massachusetts Institute of Technology
MohammadTaghi Hajiaghayi, Massachusetts Institute of Technology
Dimitrios M. Thilikos, Universitat Polit\`ecnica de Catalunya
Bounded-Degree Independent Sets in Planar Graphs
Therese Biedl, University of Waterloo
Dana Wilkinson, University of Waterloo
Queaps
John Iacono, Polytechnic University
Stefan Langerman, McGill University
A geometric approach to Boolean matrix multiplication
Andrzej Lingas, Department of Computer Science, Lund University
A Simple Memory-Efficient Bounded Concurrent Timestamping Algorithm
Vivek Shikaripura, University of Illinois at Chicago
Ajay Kshemkalyani, University of Illinois at Chicago
Maximizing a Voronoi Region: The Convex Case
Frank Dehne, Carleton University
Rolf Klein , Universitaet Bonn
Raimund Seidel, Universitaet des Saarlandes
Approximating MIN k-SAT
Adi Avidor, Tel Aviv University
Uri Zwick, Tel Aviv University
Funnel Heap - A Cache Oblivious Priority Queue
Gerth Stølting Brodal, BRICS, Department of Computer Science, University of Aarhus
Rolf Fagerberg, BRICS, Department of Computer Science, University of Aarhus
Simultaneous Embedding of a Planar Graph and Its Dual on the Grid
Cesim Erten, University of Arizona
Stephen G. Kobourov, University of Arizona
Average-Case Competitive Analyses for Ski-Rental Problems
Hiroshi Fujiwara, Kyoto University
Kazuo Iwama, Kyoto University
Minimum edge ranking spanning trees of threshold graphs
Kazuhisa Makino, Osaka University
Yushi Uno, Osaka Prefecture University
Toshihide Ibaraki, Kyoto University
History Independent Data Structures
Jason Hartline, University of Washington
Edwin Hong, University of Washington
Alexander Mohr, University of Washington
William Pentney, University of Washington
Emily Rocke, University of Washington
The Min-Max Voronoi Diagram of Polygons and Applications in VLSI Manufacturing
D. T. Lee, Academia Sinica
E. Papadopoulou, IBM TJ Watson Research Center