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