20. ISAAC 2009: Honolulu, Hawaii, USA

• Ronald L. Graham:
  Bubblesort and Juggling Sequences. 1
  
• Naoki Katoh:
  A Proof of the Molecular Conjecture. 2-3
  
• Nicolas Bourgeois, Federico Della Croce, Bruno Escoffier, Vangelis Th. Paschos:
  Exact Algorithms for Dominating Clique Problems. 4-13
  
• Tomoki Imada, Shunsuke Ota, Hiroshi Nagamochi, Tatsuya Akutsu:
  Enumerating Stereoisomers of Tree Structured Molecules Using Dynamic Programming. 14-23
  
• Sang Won Bae, Sunghee Choi, Chunseok Lee, Shin-ichi Tanigawa:
  Exact Algorithms for the Bottleneck Steiner Tree Problem. 24-33
  
• Qiang-Sheng Hua, Dongxiao Yu, Francis C. M. Lau, Yuexuan Wang:
  Exact Algorithms for Set Multicover and Multiset Multicover Problems. 34-44
  
• Francisco Claude, Reza Dorrigiv, Stephane Durocher, Robert Fraser, Alejandro López-Ortiz, Alejandro Salinger:
  Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm. 45-54
  
• Kazumasa Okumoto, Takuro Fukunaga, Hiroshi Nagamochi:
  Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems. 55-64
  
• Shuai Cheng Li, Yen Kaow Ng:
  On Protein Structure Alignment under Distance Constraint. 65-76
  
• Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prädel, Maxim Sviridenko:
  A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability. 77-86
  
• Telikepalli Kavitha, Julián Mestre:
  Max-Coloring Paths: Tight Bounds and Extensions. 87-96
  
• Yam Ki Cheung, Ovidiu Daescu:
  Fréchet Distance Problems in Weighted Regions. 97-111
  
• Daniel Andersson, Peter Bro Miltersen:
  The Complexity of Solving Stochastic Games on Graphs. 112-121
  
• Chuzo Iwamoto, Kento Sasaki, Kenji Nishio, Kenichi Morita:
  Computational Complexity of Cast Puzzles. 122-131
  
• Adrian Dumitrescu, Csaba D. Tóth:
  New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body. 132-141
  
• Shiteng Chen, Zhiyi Huang, Sampath Kannan:
  Reconstructing Numbers from Pairwise Function Values. 142-152
  
• Kristoffer Arnsfelt Hansen, Oded Lachish, Peter Bro Miltersen:
  Hilbert's Thirteenth Problem and Circuit Complexity. 153-162
  
• Jens M. Schmidt:
  Interval Stabbing Problems in Small Integer Ranges. 163-172
  
• Gerth Stølting Brodal, Rolf Fagerberg, Mark Greve, Alejandro López-Ortiz:
  Online Sorted Range Reporting. 173-182
  
• Yakov Nekrich:
  Data Structures for Approximate Orthogonal Range Counting. 183-192
  
• Gerth Stølting Brodal, Alexis C. Kaporis, Spyros Sioutas, Konstantinos Tsakalidis, Kostas Tsichlas:
  Dynamic 3-Sided Planar Range Queries with Expected Doubly Logarithmic Time. 193-202
  
• Diego Arroyuelo, Francisco Claude, Reza Dorrigiv, Stephane Durocher, Meng He, Alejandro López-Ortiz, J. Ian Munro, Patrick K. Nicholson, Alejandro Salinger, Matthew Skala:
  Untangled Monotonic Chains and Adaptive Range Search. 203-212
  
• Sanjiv Kapoor, Xiang-Yang Li:
  Geodesic Spanners on Polyhedral Surfaces. 213-223
  
• Danny Z. Chen, Haitao Wang:
  Approximating Points by a Piecewise Linear Function: I. 224-233
  
• Danny Z. Chen, Haitao Wang:
  Approximating Points by a Piecewise Linear Function: II. Dealing with Outliers. 234-243
  
• Jinhui Xu, Lei Xu, Evanthia Papadopoulou:
  Computing the Map of Geometric Minimal Cuts. 244-254
  
• Rudolf Fleischer, Yihui Wang:
  On the Camera Placement Problem. 255-264
  
• Takuro Fukunaga:
  Graph Orientations with Set Connectivity Requirements. 265-274
  
• Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Stéphan Thomassé:
  A Linear Vertex Kernel for Maximum Internal Spanning Tree. 275-282
  
• Dae Young Seo, D. T. Lee, Tien-Ching Lin:
  Geometric Minimum Diameter Minimum Cost Spanning Tree Problem. 283-292
  
• Yusuke Kobayashi, Christian Sommer:
  On Shortest Disjoint Paths in Planar Graphs. 293-302
  
• Tai-Hsin Hsu, Hsueh-I Lu:
  An Optimal Labeling for Node Connectivity. 303-310
  
• Ping Xu, Xiang-Yang Li:
  SOFA: Strategyproof Online Frequency Allocation for Multihop Wireless Networks. 311-320
  
• Francis Y. L. Chin, Hing-Fung Ting, Yong Zhang:
  1-Bounded Space Algorithms for 2-Dimensional Bin Packing. 321-330
  
• Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královic, Richard Královic, Tobias Mömke:
  On the Advice Complexity of Online Problems. 331-340
  
• Xin Han, Kazuhisa Makino:
  Online Knapsack Problems with Limited Cuts. 341-351
  
• Annamária Kovács, Ulrich Meyer, Gabriel Moruz, Andrei Negoescu:
  Online paging for flash memory devices. 352-361
  
• Imran A. Pirwani:
  Shifting Strategy for Geometric Graphs without Geometry. 362-371
  
• Minming Li:
  Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics. 372-382
  
• Zhou Xu, Liang Xu:
  Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time. 383-392
  
• Sándor P. Fekete, Joseph S. B. Mitchell, Christiane Schmidt:
  Minimum Covering with Travel Cost. 393-402
  
• Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, Ryuhei Uehara:
  Route-Enabling Graph Orientation Problems. 403-412
  
• Khaled M. Elbassioni, Hans Raj Tiwary:
  Complexity of Approximating the Vertex Centroid of a Polyhedron. 413-422
  
• Telikepalli Kavitha, Meghana Nasre:
  Popular Matchings with Variable Job Capacities. 423-433
  
• Shengyu Zhang:
  On the Tightness of the Buhrman-Cleve-Wigderson Simulation. 434-440
  
• Johannes Schneider, Roger Wattenhofer:
  Bounds on Contention Management Algorithms. 441-451
  
• Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Stefan Langerman, Ryuhei Uehara:
  Algorithmic Folding Complexity. 452-461
  
• Weiwei Wu, Minming Li, Enhong Chen:
  Min-Energy Scheduling for Aligned Jobs in Accelerate Model. 462-472
  
• Toshimasa Ishii, Kazuhisa Makino:
  Posi-modular Systems with Modulotone Requirements under Permutation Constraints. 473-482
  
• Deepanjan Kesh, Shashank K. Mehta:
  Generalized Reduction to Compute Toric Ideals. 483-492
  
• Li Chen, Bin Fu:
  Linear and Sublinear Time Algorithms for Basis of Abelian Groups. 493-502
  
• Raphael Eidenbenz, Roger Wattenhofer:
  Good Programming in Transactional Memory. 503-513
  
• Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos:
  Induced Packing of Odd Cycles in a Planar Graph. 514-523
  
• Naoki Katoh, Shin-ichi Tanigawa:
  On the Infinitesimal Rigidity of Bar-and-Slider Frameworks. 524-533
  
• Paola Flocchini, Bernard Mans, Nicola Santoro:
  Exploration of Periodically Varying Graphs. 534-543
  
• Jiong Guo, Rolf Niedermeier, Ondrej Suchý:
  Parameterized Complexity of Arc-Weighted Directed Steiner Problems. 544-553
  
• Yoshitaka Nakao, Hiroshi Nagamochi:
  Worst Case Analysis for Pickup and Delivery Problems with Consecutive Pickups and Deliveries. 554-563
  
• Tsung-Hao Liu, Hsueh-I Lu:
  Minimum Cycle Bases of Weighted Outerplanar Graphs. 564-572
  
• Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Daniel Meister, Saket Saurabh:
  Bandwidth on AT-Free Graphs. 573-582
  
• Jiong Guo, Iyad A. Kanj, Christian Komusiewicz, Johannes Uhlmann:
  Editing Graphs into Disjoint Unions of Dense Clusters. 583-593
  
• Daniel Bruce, Chính T. Hoàng, Joe Sawada:
  A Certifying Algorithm for 3-Colorability of P₅-Free Graphs. 594-604
  
• Takehiro Ito, Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos:
  Parameterizing Cut Sets in a Graph by the Number of Their Components. 605-615
  
• Minghui Jiang:
  Inapproximability of Maximal Strip Recovery. 616-625
  
• Marek Karpinski, Andrzej Rucinski, Edyta Szymanska:
  The Complexity of Perfect Matching Problems on Dense Hypergraphs. 626-636
  
• Vikraman Arvind, Pushkar S. Joglekar, Srikanth Srinivasan:
  On Lower Bounds for Constant Width Arithmetic Circuits. 637-646
  
• Xi Chen, Shang-Hua Teng:
  Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria. 647-656
  
• Paul Bell, Igor Potapov:
  The Identity Correspondence Problem and Its Applications. 657-667
  
• Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymanska:
  Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs. 668-678
  
• Daisuke Yamaguchi, Shinji Imahori, Ryuhei Miyashiro, Tomomi Matsui:
  An Improved Approximation Algorithm for the Traveling Tournament Problem. 679-688
  
• Shihong Xu, Hong Shen:
  The Fault-Tolerant Facility Allocation Problem. 689-698
  
• Minming Li, Peng-Jun Wan, F. Frances Yao:
  Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks. 699-709
  
• Laurent Bulteau, Guillaume Fertin, Irena Rusu:
  Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms. 710-719
  
• Christian Knauer, Maarten Löffler, Marc Scherfenberg, Thomas Wolle:
  The Directed Hausdorff Distance between Imprecise Point Sets. 720-729
  
• Gunnar Carlsson, Gurjeet Singh, Afra Zomorodian:
  Computing Multidimensional Persistence. 730-739
  
• Danny Z. Chen, Haitao Wang:
  Locating an Obnoxious Line among Planar Objects. 740-749
  
• Paul S. Bonsma, Felix Breuer:
  Finding Fullerene Patches in Polynomial Time. 750-759
  
• Xiao Zhou, Takao Nishizeki:
  Convex Drawings of Internally Triconnected Plane Graphs on O(n²) Grids. 760-770
  
• Riko Jacob, Stephan Ritscher, Christian Scheideler, Stefan Schmid:
  A Self-stabilizing and Local Delaunay Graph Construction. 771-780
  
• Michael T. Goodrich, Darren Strash:
  Succinct Greedy Geometric Routing in the Euclidean Plane. 781-791
  
• Jonathan A. Kelner, Petar Maymounkov:
  Electric Routing and Concurrent Flow Cutting. 792-801
  
• Naoyuki Kamiyama, Naoki Katoh:
  A Polynomial-Time Algorithm for the Universally Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths. 802-811
  
• Benjamin Doerr, Anna Huber, Ariel Levavi:
  Strong Robustness of Randomized Rumor Spreading Protocols. 812-821
  
• Gerth Stølting Brodal, Allan Grønlund Jørgensen:
  Data Structures for Range Median Queries. 822-831
  
• Siddhartha Sen, Robert Endre Tarjan:
  Deletion without Rebalancing in Multiway Search Trees. 832-841
  
• Gerth Stølting Brodal, Allan Grønlund Jørgensen, Gabriel Moruz, Thomas Mølhave:
  Counting in the Presence of Memory Faults. 842-851
  
• Scott Schneider, Michael Spertus:
  A Simple, Fast, and Compact Static Dictionary. 852-861
  
• Therese C. Biedl, Stephane Durocher, Jack Snoeyink:
  Reconstructing Polygons from Scanner Data. 862-871
  
• Robert Franke, Ignaz Rutter, Dorothea Wagner:
  Computing Large Matchings in Planar Graphs with Fixed Minimum Degree. 872-881
  
• Tamara Mchedlidze, Antonios Symvonis:
  Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs. 882-891
  
• Cristina Bazgan, Basile Couëtoux, Zsolt Tuza:
  Covering a Graph with a Constrained Forest (Extended Abstract). 892-901
  
• Marwan Al-Jubeh, Mashhood Ishaque, Kristóf Rédei, Diane L. Souvaine, Csaba D. Tóth:
  Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs. 902-912
  
• Seok-Hee Hong, Hiroshi Nagamochi:
  Upward Star-Shaped Polyhedral Graphs. 913-922
  
• Linqing Tang:
  Conditional Hardness of Approximating Satisfiable Max 3CSP-q. 923-932
  
• Tomoyuki Yamakami:
  The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract). 933-942
  
• Dan Alistarh, Seth Gilbert, Rachid Guerraoui, Corentin Travers:
  Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement. 943-953
  
• Ján Manuch, Ladislav Stacho, Christine Stoll:
  Step-Assembly with a Constant Number of Tile Types. 954-963
  
• Donald Stanley, Boting Yang:
  Lower Bounds on Fast Searching. 964-973
  
• Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, Chaitanya Swamy:
  Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity. 974-983
  
• Qian-Ping Gu, Hisao Tamaki:
  Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n^{1 + ε}) Time. 984-993
  
• Anna Adamaszek, Artur Czumaj, Andrzej Lingas:
  PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k. 994-1003
  
• Tien-Ching Lin, D. T. Lee:
  Optimal Randomized Algorithm for the Density Selection Problem. 1004-1013
  
• Decheng Dai, Rong Ge:
  New Results on Simple Stochastic Games. 1014-1023
  
• Bodo Manthey, Heiko Röglin:
  Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences. 1024-1033
  
• Wing-Kai Hon, Tak Wah Lam, Rahul Shah, Siu-Lung Tam, Jeffrey Scott Vitter:
  Succinct Index for Dynamic Dictionary Matching. 1034-1043
  
• Hagai Cohen, Ely Porat:
  Range Non-overlapping Indexing. 1044-1053
  
• Sang Won Bae, Yoshio Okamoto:
  Querying Two Boundary Points for Shortest Paths in a Polygonal Domain. 1054-1063
  
• Sylvain Guillemot, Stéphane Vialette:
  Pattern Matching for 321-Avoiding Permutations. 1064-1073
  
• Erik D. Demaine, Martin L. Demaine, Goran Konjevod, Robert J. Lang:
  Folding a Better Checkerboard. 1074-1083
  
• Ping-Hui Hsu, Kuan-Yu Chen, Kun-Mao Chao:
  Finding All Approximate Gapped Palindromes. 1084-1093
  
• George Karakostas:
  General Pseudo-random Generators from Weaker Models of Computation. 1094-1103
  
• Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara:
  Random Generation and Enumeration of Bipartite Permutation Graphs. 1104-1113
  
• R. Chandrasekaran, K. Subramani:
  A Combinatorial Algorithm for Horn Programs. 1114-1123
  
• Amotz Bar-Noy, Michael Lampis:
  Online Maximum Directed Cut. 1124-1133
  
• Minkyoung Cho, David M. Mount, Eunhui Park:
  Maintaining Nets and Net Trees under Incremental Motion. 1134-1143
  
• Shivali Agarwal, Ankur Narang, R. K. Shyamasundar:
  Distributed Scheduling of Parallel Hybrid Computations. 1144-1154
  
• Lars Arge, Morten Revsbæk:
  I/O-Efficient Contour Tree Simplification. 1155-1165
  
• Jinhee Chun, Ryosei Kasai, Matias Korman, Takeshi Tokuyama:
  Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes. 1166-1174
  
• Craig Dillabaugh, Meng He, Anil Maheshwari, Norbert Zeh:
  I/O and Space-Efficient Path Traversal in Planar Graphs. 1175-1184
  
• Jin Wook Kim, Siwon Choi, Joong Chae Na, Jeong Seop Sim:
  Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model. 1185-1194
  
• Pei-Chi Huang, Hsin-Wen Wei, Yen-Chiu Chen, Ming-Yang Kao, Wei Kuan Shih, Tsan-sheng Hsu:
  Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint (Extended Abstract). 1195-1204
  
• Sylvain Guillemot, Jesper Jansson, Wing-Kin Sung:
  Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets. 1205-1214
  
• Daniël Paulusma, Johan M. M. van Rooij:
  On Partitioning a Graph into Two Connected Subgraphs. 1215-1224
  

Last update Wed Feb 15 05:10:29 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page