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 |
|