16. ISAAC 2005: Sanya, Hainan, China

• F. Frances Yao:
  Algorithmic Problems in Wireless Ad Hoc Networks. 1
  
• Kousha Etessami, Mihalis Yannakakis:
  Probability and Recursion. 2-4
  
• Annette Ebbers-Baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas:
  Embedding Point Sets into Plane Graphs of Small Dilation. 5-16
  
• Xiaodong Wu, Danny Z. Chen, Kang Li, Milan Sonka:
  The Layered Net Surface Problems in Discrete Geometry and Medical Image Segmentation. 17-27
  
• Sariel Har-Peled, Vladlen Koltun:
  Separability with Outliers. 28-39
  
• Hee-Kap Ahn, Sang Won Bae, Siu-Wing Cheng, Kyung-Yong Chwa:
  Casting an Object with a Core. 40-49
  
• Boris Aronov, Mark de Berg, Otfried Cheong, Joachim Gudmundsson, Herman J. Haverkort, Antoine Vigneron:
  Sparse Geometric Graphs with Small Dilation. 50-59
  
• Mirela Tanase, Remco C. Veltkamp, Herman J. Haverkort:
  Multiple Polyline to Polygon Matching. 60-70
  
• Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige:
  Minimizing a Monotone Concave Function with Laminar Covering Constraints. 71-81
  
• Mingen Lin, Zhiyong Lin, Jinhui Xu:
  Almost Optimal Solutions for Bin Coloring Problems. 82-91
  
• Ying Xiao, Krishnaiyan Thulasiraman, Guoliang Xue:
  GEN-LARAC: A Generalized Approach to the Constrained Shortest Path Problem Under Multiple Additive Constraints. 92-105
  
• Khaled M. Elbassioni, Irit Katriel, Martin Kutz, Meena Mahajan:
  Simultaneous Matchings. 106-115
  
• Tsunehiko Kameda, Yi Sun, Luis A. Goddyn:
  An Optimization Problem Related to VoD Broadcasting. 116-125
  
• Xujin Chen, Guoli Ding, Xiaodong Hu, Wenan Zang:
  A Min-Max Relation on Packing Feedback Vertex Sets. 126-135
  
• Ming-Yang Kao, Xiang-Yang Li, Weizhao Wang:
  Average Case Analysis for Tree Labelling Schemes. 136-145
  
• Binh-Minh Bui-Xuan, Michel Habib, Christophe Paul:
  Revisiting T. Uno and M. Yagiura's Algorithm . 146-155
  
• Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino:
  Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs. 156-165
  
• Xiao Zhou, Takao Nishizeki:
  Orthogonal Drawings of Series-Parallel Graphs with Minimum Bends. 166-175
  
• Toshimasa Ishii, Kengo Iwata, Hiroshi Nagamochi:
  Bisecting a Four-Connected Graph with Three Resource Sets. 176-185
  
• Ryuhei Uehara, Yushi Uno:
  Laminar Structure of Ptolemaic Graphs and Its Applications. 186-195
  
• Zdenek Dvorak, Vít Jelínek:
  On the Complexity of the G-Reconstruction Problem. 196-205
  
• Edith Elkind, Helger Lipmaa:
  Hybrid Voting Protocols and Hardness of Manipulation. 206-215
  
• Zhixiang Chen, Bin Fu:
  On the Complexity of Rocchio's Similarity-Based Relevance Feedback Algorithm. 216-225
  
• Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Tao Jiang:
  Correlation Clustering and Consensus Clustering. 226-235
  
• Klaus Jansen, Hu Zhang:
  An Approximation Algorithm for Scheduling Malleable Tasks Under General Precedence Constraints. 236-245
  
• Sebastian Seibert, Walter Unger:
  A 1.5-Approximation of the Minimal Manhattan Network Problem. 246-255
  
• Matthias Müller-Hannemann, Anna Schulze:
  Hardness and Approximation of Octilinear Steiner Trees. 256-265
  
• Akiko Suzuki, Takeshi Tokuyama:
  Dense Subgraph Problems with Output-Density Conditions. 266-276
  
• Yvo Desmedt, Yongge Wang, Mike Burmester:
  A Complete Characterization of Tolerable Adversary Structures for Secure Point-to-Point Transmissions Without Feedback. 277-287
  
• Marios Mavronicolas, Vicky G. Papadopoulou, Anna Philippou, Paul G. Spirakis:
  Network Game with Attacker and Protector Entities. 288-297
  
• Saeed Alaei, Mohammad Toossi, Mohammad Ghodsi:
  SkipTree: A Scalable Range-Queryable Distributed Data Structure for Multidimensional Data. 298-307
  
• Peter Høyer:
  The Phase Matrix. 308-317
  
• Alexis C. Kaporis, Christos Makris, George Mavritsakis, Spyros Sioutas, Athanasios K. Tsakalidis, Kostas Tsichlas, Christos D. Zaroliagis:
  ISB-Tree: A New Indexing Scheme with Efficient Expected Behaviour. 318-327
  
• Lars Arge, Laura Toma:
  External Data Structures for Shortest Path Queries on Planar Digraphs. 328-338
  
• Tak Wah Lam, Wing-Kin Sung, Swee-Seong Wong:
  Improved Approximate String Matching Using Compressed Suffix Data Structures. 339-348
  
• Pankaj K. Agarwal, Junyi Xie, Jun Yang, Hai Yu:
  Monitoring Continuous Band-Join Queries over Dynamic Data. 349-359
  
• Ying Kit Lai, Chung Keung Poon, Benyun Shi:
  Approximate Colored Range Queries. 360-369
  
• Lan Liu, Xi Chen, Jing Xiao, Tao Jiang:
  Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem. 370-379
  
• Lusheng Wang, Kaizhong Zhang:
  Space Efficient Algorithms for Ordered Tree Comparison. 380-391
  
• Yun Cui, Lusheng Wang, Daming Zhu:
  A 1.75-Approximation Algorithm for Unsigned Translocation Distance. 392-401
  
• Nguyen Bao Nguyen, C. Thach Nguyen, Wing-Kin Sung:
  Fast Algorithms for Computing the Tripartition-Based Distance Between Phylogenetic Networks. 402-411
  
• Hao Yuan, Linji Yang, Erdong Chen:
  Improved Algorithms for Largest Cardinality 2-Interval Pattern Problem. 412-421
  
• Yong He, Yiwei Jiang:
  Preemptive Semi-online Scheduling on Parallel Machines with Inexact Partial Information. 422-432
  
• Marc Demange, Bernard Kouakou, Éric Soutif:
  On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems. 433-442
  
• Lean Yu, Shouyang Wang, Kin Keung Lai:
  A Novel Adaptive Learning Algorithm for Stock Market Prediction. 443-452
  
• Lei Yang:
  Uniformization of Discrete Data. 453-462
  
• Li-Sha Huang:
  A Practical Algorithm for the Computation of Market Equilibrium with Logarithmic Utility Functions. 463-472
  
• Joachim Giesen, Dieter Mitsche:
  Boosting Spectral Partitioning by Sampling and Iteration. 473-482
  
• Bodo Manthey, Rüdiger Reischuk:
  Smoothed Analysis of Binary Search Trees. 483-492
  
• Christoforos Raptopoulos, Paul G. Spirakis:
  Simple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection Graphs. 493-504
  
• Sumit Ganguly:
  Counting Distinct Items over Update Streams. 505-514
  
• Tien-Ching Lin, D. T. Lee:
  Randomized Algorithm for the Sum Selection Problem. 515-523
  
• Martin Nehéz, Daniel Olejár:
  An Improved Interval Routing Scheme for Almost All Networks Based on Dominating Cliques. 524-532
  
• Ioannis Caragiannis, Clemente Galdi, Christos Kaklamanis:
  Basic Computations in Wireless Networks. 533-542
  
• Sanguthevar Rajasekaran, Sandeep Sen:
  A Simple Optimal Randomized Algorithm for Sorting on the PDM. 543-552
  
• Yan Wang, Deqiang Wang, Wei Liu, Baoyu Tian:
  Efficient Parallel Algorithms for Constructing a k-Tree Center and a k-Tree Core of a Tree Network. 553-562
  
• Satoshi Fujita:
  A Tight Bound on the Number of Mobile Servers to Guarantee the Mutual Transferability Among Dominating Configurations. 563-572
  
• Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, Alexey A. Stepanov:
  Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach. 573-582
  
• Feodor F. Dragan, Chenyu Yan:
  Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-Width, or Clique-Width. 583-592
  
• Manuel Bodirsky, Clemens Gröpl, Mihyun Kang:
  Sampling Unlabeled Biconnected Planar Graphs. 593-603
  
• Christian Knauer, Étienne Schramm, Andreas Spillner, Alexander Wolff:
  Configurations with Few Crossings in Topological Graphs. 604-613
  
• Adrian Kosowski, Michal Malafiejski, Pawel Zylinski:
  On Bounded Load Routings for Modeling k-Regular Connection Topologies. 614-623
  
• Cristina Bazgan, Marek Karpinski:
  On the Complexity of Global Constraint Satisfaction. 624-633
  
• Carme Àlvarez, Joaquim Gabarró, Maria J. Serna:
  Polynomial Space Suffices for Deciding Nash Equilibria Properties for Extensive Games with Large Trees, . 634-643
  
• Masaki Yamamoto:
  An Improved O(1.234^m)-Time Deterministic Algorithm for SAT. 644-653
  
• Stefan Porschen:
  Solving Minimum Weight Exact Satisfiability in Time O(2^0.2441n). 654-664
  
• Wun-Tat Chan, Yong Zhang, Stanley P. Y. Fung, Deshi Ye, Hong Zhu:
  Efficient Algorithms for Finding a Longest Common Increasing Subsequence. 665-674
  
• Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking:
  Decision Making Based on Approximate and Smoothed Pareto Curves. 675-684
  
• Federico Della Croce, Vangelis Th. Paschos:
  Computing Optimal Solutions for the min 3-set covering Problem. 685-692
  
• Boaz Ben-Moshe, Binay K. Bhattacharya, Qiaosheng Shi:
  Efficient Algorithms for the Weighted 2-Center Problem in a Cactus Graph. 693-703
  
• Zeshan Peng:
  Algorithms for Local Forest Similarity. 704-713
  
• Anders Bergkvist, Peter Damaschke:
  Fast Algorithms for Finding Disjoint Subsequences with Extremal Densities. 714-723
  
• Hiroki Arimura, Takeaki Uno:
  A Polynomial Space and Polynomial Delay Algorithm for Enumeration of Maximal Motifs in a Sequence. 724-737
  
• William S. Kennedy, Guohui Lin:
  5-th Phylogenetic Root Construction for Strictly Chordal Graphs. 738-747
  
• Kenya Ueno:
  Recursion Theoretic Operators for Function Complexity Classes. 748-756
  
• Ralf Klasing, Zvi Lotker, Alfredo Navarra, Stephane Perennes:
  From Balls and Bins to Points and Vertices. 757-766
  
• Pinyan Lu, Jialin Zhang, Chung Keung Poon, Jin-yi Cai:
  Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs. 767-776
  
• Damien Woods:
  Upper Bounds on the Computational Power of an Optical Model of Computation. 777-788
  
• Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten:
  Complexity of the Min-Max (Regret) Versions of Cut Problems. 789-798
  
• Chih-Huai Cheng, Kuan-Yu Chen, Wen-Chin Tien, Kun-Mao Chao:
  Improved Algorithms for the k Maximum-Sums Problems. 799-808
  
• Ioannis Caragiannis, Clemente Galdi, Christos Kaklamanis:
  Network Load Games. 809-818
  
• Jean Cardinal, Samuel Fiorini, Gwenaël Joret:
  Minimum Entropy Coloring. 819-828
  
• Vilhelm Dahllöf:
  Algorithms for Max Hamming Exact Satisfiability. 829-838
  
• Spyros C. Kontogiannis, Paul G. Spirakis:
  Counting Stable Strategies in Random Evolutionary Games. 839-848
  
• Rolf Klein, Christian Knauer, Giri Narasimhan, Michiel H. M. Smid:
  Exact and Approximation Algorithms for Computing the Dilation Spectrum of Paths, Trees, and Cycles. 849-858
  
• Chris Worman, Boting Yang:
  On the Computation of Colored Domino Tilings of Simple and Non-simple Orthogonal Polygons. 859-868
  
• Joel Fenwick, Vladimir Estivill-Castro:
  Optimal Paths for Mutually Visible Agents. 869-881
  
• Hee-Kap Ahn, Otfried Cheong:
  Stacking and Bundling Two Convex Polygons. 882-891
  
• Prosenjit Gupta:
  Algorithms for Range-Aggregate Query Problems Involving Geometric Aggregation Operations. 892-901
  
• Kazuo Iwama, Shuichi Miyazaki, Naoya Yamauchi:
  A (2-c*(1/sqrt(N)))-Approximation Algorithm for the Stable Marriage Problem. 902-914
  
• Michele Flammini, Luca Moscardelli, Mordechai Shalom, Shmuel Zaks:
  Approximating the Traffic Grooming Problem. 915-924
  
• Liying Kang, T. C. Edwin Cheng, C. T. Ng, Min Zhao:
  Scheduling to Minimize Makespan with Time-Dependent Processing Times. 925-933
  
• Jérôme Monnot:
  On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems. 934-943
  
• Sun-Yuan Hsieh, Ting-Yu Chou:
  Finding a Weight-Constrained Maximum-Density Subtree in a Tree. 944-953
  
• Bing Yang, S. Q. Zheng, Enyue Lu:
  Finding Two Disjoint Paths in a Network with Normalized alpha⁺-MIN-SUM Objective Function. 954-963
  
• Seth Pettie:
  Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time. 964-973
  
• Qingbo Cai, Vincenzo Liberatore:
  Approximation Algorithms for Layered Multicast Scheduling. 974-983
  
• Magdalene Grantson, Christian Borgelt, Christos Levcopoulos:
  Minimum Weight Triangulation by Cutting Out Triangles. 984-994
  
• Bin Fu, Sorinel Adrian Oprisan, Lizhe Xu:
  Multi-directional Width-Bounded Geometric Separator and Protein Folding. 995-1006
  
• Sang Won Bae, Kyung-Yong Chwa:
  Shortest Paths and Voronoi Diagrams with Transportation Networks Under General Distances. 1007-1018
  
• Oliver Klein, Remco C. Veltkamp:
  Approximation Algorithms for Computing the Earth Mover's Distance Under Transformations. 1019-1028
  
• Mingjun Song, Sanguthevar Rajasekaran:
  Fast k-Means Algorithms with Constant Approximation. 1029-1038
  
• Aleksei V. Fishkin, Olga Gerber, Klaus Jansen:
  On Efficient Weighted Rectangle Packing with Large Resources. 1039-1050
  
• Tamás Terlaky, Anthony Vannelli, Hu Zhang:
  On Routing in VLSI Design and Communication Networks. 1051-1060
  
• Andrew Lim, Fan Wang, Zhou Xu:
  The Capacitated Traveling Salesman Problem with Pickups and Deliveries on a Tree. 1061-1070
  
• Cyril Gavoille, Olivier Ly:
  Distance Labeling in Hyperbolic Graphs. 1071-1079
  
• Paraskevi Fragopoulou, Stavros D. Nikolopoulos, Leonidas Palios:
  Multi-source Trees: Algorithms for Minimizing Eccentricity Cost Metrics. 1080-1089
  
• Jianxi Fan, Xiaola Lin, Xiaohua Jia, Rynson W. H. Lau:
  Edge-Pancyclicity of Twisted Cubes. 1090-1099
  
• Stefan Eckhardt, Sven Kosub, Moritz G. Maaß, Hanjo Täubig, Sebastian Wernicke:
  Combinatorial Network Abstraction by Trees and Distances. 1100-1109
  
• Christian Bachmaier, Ulrik Brandes, Barbara Schlieper:
  Drawing Phylogenetic Trees. 1110-1121
  
• Fabrice Bazzaro, Cyril Gavoille:
  Localized and Compact Data-Structure for Comparability Graphs. 1122-1131
  
• Robin Nunkesser, Philipp Woelfel:
  Representation of Graphs by OBDDs. 1132-1142
  
• Diego Arroyuelo, Gonzalo Navarro:
  Space-Efficient Construction of LZ-Index. 1143-1152
  
• Erdong Chen, Hao Yuan, Linji Yang:
  Longest Increasing Subsequences in Windows Based on Canonical Antichain Partition. 1153-1162
  

Errata from ISAAC 2004 (LNCS 3341)

• David J. Abraham, Katarína Cechlárová, David Manlove, Kurt Mehlhorn:
  Pareto Optimality in House Allocation Problems. 1163-1175
  
• Danny Z. Chen, Xiaobo Sharon Hu, Shuang (Sean) Luan, Shahid A. Naqvi, Chao Wang, Cedric X. Yu:
  Generalized Geometric Approaches for Leaf Sequencing Problems in Radiation Therapy. 1176-1186
  

Last update Mon Feb 13 04:34:27 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page