Computing and Combinatorics: 26th International Conference, Cocoon 2020, Atlanta, Ga, Usa, August 29-31, 2020, Proceedings

ISBN-13: 9783030581497 / Angielski / Miękka / 2020 / 678 str.

Donghyun Kim; R. N. Uma; Zhipeng Cai

Spis treści

Subspace approximation with outliers.- Linear-time Algorithms for Eliminating Claws in Graphs.- A new lower bound for the eternal vertex cover number of graphs.- Bounded-Degree Spanners in the Presence of Polygonal Obstacles.- End-Vertices of AT-free Bigraphs.- Approaching Optimal Duplicate Detection in a Sliding Window.- Computational Complexity Characterization of Protecting Elections from Bribery.- Coding with Noiseless Feedback over the Z-channel.- Path-monotonic Upward Drawings of Plane Graphs.- Seamless Interpolation between Contraction Hierarchies and Hub Labels for fast and space-e cient Shortest Path Queries in Road Networks.- Visibility polygon queries among dynamic polygonal obstacles in plane.- How Hard is Completeness Reasoning for Conjunctive Queries?.- Imbalance Parameterized by Twin Cover Revisited.- Local Routing in a Tree Metric 1-Spanner.- Deep Specification Mining with Attention.- Constructing Independent Spanning Trees in Alternating Group Networks.- W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension.- An Optimal Lower Bound for Hierarchical Universal Solutions for TSP on the Plane.- Quantum Speedup for the Minimum Steiner Tree Problem.- Access Structure Hiding Secret Sharing from Novel Set Systems and Vector Families.- Approximation algorithms for car-sharing problems.- Realization Problems on Reachability Sequences.- Power of Decision Trees with Monotone Queries.- Computing a maximum clique in geometric superclasses of disk graphs.- Visibility.- Tight approximation for the minimum bottleneck generalized matching problem.- Graph Classes and Approximability of the Happy Set Problem.- A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs.- Uniqueness of $DP$-Nash Subgraphs and $D$-sets.- On the Enumeration of Minimal Non-Pairwise Compatibility Graphs.- Constructing Tree Decompositions of Graphs with Bounded Gonality.- Election Control through Social In uence with Unknown Preferences.- New Symmetry-less ILP Formulation for the Classical One Dimensional Bin-Packing Problem.- On the Area Requirements of Planar Greedy Drawings of Triconnected Planar Graphs.- On the Restricted 1-Steiner Tree Problem.- Computational Complexity of Synchronization under Regular Commutative Constraints.- Approximation algorithms for general cluster routing problem.- Hardness of Sparse Sets and Minimal Circuit Size Problem.- Succinct Monotone Circuit Certi cation: Planarity and Parameterized Complexity.- On Measures of Space Over Real and Complex Numbers.- Parallelized maximization of nonsubmodular function subject to a cardinality constraint.- An improved Bregman $k$-means++ algorithm via local search.- On the Complexity of Directed Intersection Representation of DAGs.- On the Mystery of Negations in Circuits : Structure vs Power.- Even better xed-parameter algorithms for bicluster editing.- Approximate Set Union via Approximate Randomization.- A Non-Extendibility Certi cate for Submodularity and Applications.- Parameterized Complexity of Maximum Edge Colorable Subgraph.- Approximation Algorithms for the Lower-Bounded k-Median and Ist Generalizations.- A Survey for Conditional Diagnosability of Alternating Group Networks.- Fixed Parameter Tractability of Graph Deletion Problems over Data Streams.- Mixing of Markov Chains for Independent Sets on Chordal Graphs with Bounded Separators.