Limit search to available items
Book Cover
E-book
Author ISAAC (Symposium) (24th : 2013 : Hong Kong, China)

Title Algorithms and computation : 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings / edited by Leizhen Cai, Siu-Wing Cheng, Tak-Wah Lam
Published Heidelberg : Springer, 2013

Copies

Description 1 online resource (xviii, 747 pages) : illustrations
Series Lecture notes in computer science, 0302-9743 ; 8283. Advanced research in computing and software science
LNCS sublibrary. SL 1, Theoretical computer science and general issues
Lecture notes in computer science ; 8283. 0302-9743
Lecture notes in computer science. Advanced research in computing and software science.
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
Contents Invited Talk Paper. Market Approach to Social Ads: The MyLikes Example and Related Problems / Darja Krushevskaja, S. Muthukrishnan -- Session 1A: Computational Geometry I. Geodesic-Preserving Polygon Simplification / Oswin Aichholzer, Thomas Hackl, Matias Korman [and others] -- Space-Efficient and Data-Sensitive Polygon Reconstruction Algorithms from Visibility Angle Information / Jinhee Chun, Ricardo Garcia de Gonzalo, Takeshi Tokuyama -- On the Edge Crossing Properties of Euclidean Minimum Weight Laman Graphs / Sergey Bereg, Seok-Hee Hong, Naoki Katoh [and others] -- Structure and Computation of Straight Skeletons in 3-Space / Franz Aurenhammer, Gernot Walzl -- Session 1B: Pattern Matching. Pattern Matching with Non Overlapping Reversals -- Approximation and On-line Algorithms / Amihood Amir, Benny Porat -- Single and Multiple Consecutive Permutation Motif Search / Djamal Belazzougui, Adeline Pierrot, Mathieu Raffinot, Stéphane Vialette -- Beating O(nm) in Approximate LZW-Compressed Pattern Matching / Paweł Gawrychowski, Damian Straszak -- Less Space: Indexing for Queries with Wildcards / Moshe Lewenstein, J. Ian Munro, Venkatesh Raman, Sharma V. Thankachan
Session 2A: Computational Complexity I. On Determining Deep Holes of Generalized Reed-Solomon Codes / Qi Cheng, Jiyou Li, Jincheng Zhuang -- Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes / Yota Otachi, Pascal Schweitzer -- Determinantal Complexities and Field Extensions / Youming Qiao, Xiaoming Sun, Nengkun Yu -- Session 2B: Internet and Social Network Algorithms I. Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs / Matthew Johnson, Daniël Paulusma, Erik Jan van Leeuwen -- Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs / Marc Lelarge, Hang Zhou -- The Complexity of Finding a Large Subgraph under Anonymity Constraints / Robert Bredereck, Sepp Hartung, André Nichterlein, Gerhard J. Woeginger
Session 3A: Graph Theory and Algorithms I. On the Number of Edges of Fan-Crossing Free Graphs / Otfried Cheong, Sariel Har-Peled, Heuna Kim, Hyo-Sil Kim -- Cops and Robbers on Intersection Graphs / Tomás Gavenčiak, Vít Jelínek, Pavel Klavík, Jan Kratochvíl -- SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graphs / Patrizio Angelini, William Evans, Fabrizio Frati, Joachim Gudmundsson -- Hardness and Algorithms for Variants of Line Graphs of Directed Graphs / Mourad Baïou, Laurent Beaudou, Zhentao Li, Vincent Limouzy -- Session 3B: Scheduling Algorithms. Performance Guarantees for Scheduling Algorithms under Perturbed Machine Speeds / Michael Etscheid -- Better Bounds for Online k-Frame Throughput Maximization in Network Switches / Jun Kawahara, Koji M. Kobayashi, Shuichi Miyazaki -- The Solvable Cases of a Scheduling Algorithm / Sam Walker, Yakov Zinder
Session 4A: Computational Complexity II. Exact Sublinear Binomial Sampling / Martín Farach-Colton, Meng-Tsung Tsai -- Trivial, Tractable, Hard. A Not So Sudden Complexity Jump in Neighborhood Restricted CNF Formulas / Dominik Scheder -- Dynamic Point Labeling is Strongly PSPACE-Complete / Kevin Buchin, Dirk H.P. Gerrits -- Unsatisfiable CNF Formulas contain Many Conflicts / Dominik Scheder -- Session 4B: Computational Geometry II. Pursuit Evasion on Polyhedral Surfaces / Kyle Klein, Subhash Suri -- Algorithms for Tolerated Tverberg Partitions / Wolfgang Mulzer, Yannik Stein -- Abstract Voronoi Diagrams with Disconnected Regions / Cecilia Bohler, Rolf Klein -- Terrain Visibility with Multiple Viewpoints / Ferran Hurtado, Maarten Löffler, Inês Matos [and others]
Session 5A: Graph Theory and Algorithms II. Exact Algorithms for Maximum Independent Set / Mingyu Xiao, Hiroshi Nagamochi -- On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs / Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary [and others] -- Testing Mutual Duality of Planar Graphs / Patrizio Angelini, Thomas Bläsius, Ignaz Rutter -- Session 5B: Fixed-Parameter Tractable Algorithms. Effective and Efficient Data Reduction for the Subset Interconnection Design Problem / Jiehua Chen, Christian Komusiewicz, Rolf Niedermeier [and others] -- Myhill-Nerode Methods for Hypergraphs / René van Bevern, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond -- Augmenting Graphs to Minimize the Diameter / Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson, Luke Mathieson
Session 6A: Algorithms and Data Structures I. Top-k Document Retrieval in Compact Space and Near-Optimal Time / Gonzalo Navarro, Sharma V. Thankachan -- Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers / Timothy M. Chan, J. Ian Munro, Venkatesh Raman -- Trajectory-Based Dynamic Map Labeling / Andreas Gemsa, Benjamin Niedermann, Martin Nöllenburg -- Session 6B: Internet and Social Network Algorithms II. Asynchronous Rumor Spreading on Random Graphs / Konstantinos Panagiotou, Leo Speidel -- Unit Cost Buyback Problem / Yasushi Kawase, Xin Han, Kazuhisa Makino -- Faster Rumor Spreading with Multiple Calls / Konstantinos Panagiotou, Ali Pourmiri, Thomas Sauerwald
Session 7A: Algorithmic Game Theory. Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy / Søren Kristoffer Stiil Frederiksen, Peter Bro Miltersen -- Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items / Kazuo Murota, Akiyoshi Shioura, Zaifu Yang -- New Results on the Online Pricing Problem / Xiangzhong Xiang -- Session 7B: Algorithms and Data Structures II. RAM-Efficient External Memory Sorting / Lars Arge, Mikkel Thorup -- Succinct Data Structures for Representing Equivalence Classes / Moshe Lewenstein, J. Ian Munro, Venkatesh Raman -- Sliding Bloom Filters / Moni Naor, Eylon Yogev
Session 8A: Graph Theory and Algorithms III. Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs / C. Gregory Plaxton -- Bounded Representations of Interval and Proper Interval Graphs / Martin Balko, Pavel Klavík, Yota Otachi -- Detecting and Counting Small Pattern Graphs / Peter Floderus, Mirosław Kowaluk, Andrzej Lingas, Eva-Marta Lundell -- An O *(1.1939 n) Time Algorithm for Minimum Weighted Dominating Induced Matching / Min Chih Lin, Michel J. Mizrahi, Jayme L. Szwarcfiter -- Session 8B: Approximation Algorithms I. New Inapproximability Bounds for TSP / Marek Karpinski, Michael Lampis, Richard Schmied -- Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise / Bodo Manthey, Rianne Veenstra -- Tight Approximation Bounds for Connectivity with a Color-Spanning Set / Chenglin Fan, Jun Luo, Binhai Zhu -- The Train Delivery Problem Revisited / Jing Chen, He Guo, Xin Han, Kazuo Iwama
Session 9A: Computational Geometry III. The Distance 4-Sector of Two Points Is Unique / Robert Fraser, Meng He, Akitoshi Kawamura [and others] -- The Number of Different Unfoldings of Polyhedra / Takashi Horiyama, Wataru Shoji -- Computing the Smallest Color-Spanning Axis-Parallel Square / Payam Khanteimouri, Ali Mohades, Mohammad Ali Abam, Mohammad Reza Kazemi -- Session 9B: Approximation Algorithms II. Euclidean Traveling Salesman Tours through Stochastic Neighborhoods / Pegah Kamousi, Subhash Suri -- Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure / Angsheng Li, Pan Peng -- Approximate Čech Complex in Low and High Dimensions / Michael Kerber, R. Sharathkumar
Session 10A: Computational Complexity III. Model Counting for Formulas of Bounded Clique-Width / Friedrich Slivovsky, Stefan Szeider -- Computing Plurality Points and Condorcet Points in Euclidean Space / Yen-Wei Wu, Wei-Yin Lin, Hung-Lung Wang, Kun-Mao Chao -- Computing Minimum Tile Sets to Self-Assemble Color Patterns / Aleck C. Johnsen, Ming-Yang Kao, Shinnosuke Seki -- Session 10B: Network Algorithms. A Probabilistic Analysis of Kademlia Networks / Xing Shi Cai, Luc Devroye -- Approximating the Generalized Minimum Manhattan Network Problem / Aparna Das, Krzysztof Fleszar, Stephen Kobourov [and others] -- Minmax Regret 1-Facility Location on Uncertain Path Networks / Haitao Wang
Summary This book constitutes the refereed proceedings of the 24th International Symposium on Algorithms and Computation, ISAAC 2013, held in Hong Kong, China in December 2013. The 67 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 177 submissions for inclusion in the book. The focus of the volume in on the following topics: computation geometry, pattern matching, computational complexity, internet and social network algorithms, graph theory and algorithms, scheduling algorithms, fixed-parameter tractable algorithms, algorithms and data structures, algorithmic game theory, approximation algorithms and network algorithms
Notes International conference proceedings
Online resource; title from PDF title page (SpringerLink, viewed December 16, 2013)
Subject Computer algorithms -- Congresses
Computing Methodologies
Algorithms
algorithms.
Computer algorithms
Genre/Form proceedings (reports)
Conference papers and proceedings
Conference papers and proceedings.
Actes de congrès.
Form Electronic book
Author Cai, Leizhen, editor
ISBN 9783642450303
364245030X
3642450296
9783642450297
Other Titles ISAAC 2013