StringologyTimes

Data Structures and Algorithms: 2020/2/15-21

1: On the complexity of finding large odd induced subgraphs and odd colorings
2: On Extensions of Maximal Repeats in Compressed Strings
3: Sparse Coresets for SVD on Infinite Streams
4: Kruskal-based approximation algorithm for the multi-level Steiner tree problem
5: Weighted Additive Spanners
6: Coresets for the Nearest-Neighbor Rule
7: Directed Graph Hashing
8: Individual Fairness for $k$-Clustering
9: How fast can you update your MST? (Dynamic algorithms for cluster computing)
10: Computing Covers under Substring Consistent Equivalence Relations
11: Parameterized DAWGs: efficient constructions and bidirectional pattern searches
12: Detecting $k$-(Sub-)Cadences and Equidistant Subsequence Occurrences
13: Approximate Distance Oracles Subject to Multiple Vertex Failures
14: On the Power and Limits of Dynamic Pricing in Combinatorial Markets
15: Approximating Multistage Matching Problems
16: A Note on Arc-Disjoint Cycles in Bipartite Tournaments
17: Finding All Global Minimum Cuts In Practice
18: A Fast Counting Method for 6-motifs with Low Connectivity
19: Computing rank-revealing factorizations of matrices stored out-of-core
20: Pandora’s Box Problem with Order Constraints
21: Hypergraph Isomorphism for Groups with Restricted Composition Factors
22: An Experimental Study of ILP Formulations for the Longest Induced Path Problem
23: Spectrum preserving short cycle removal on regular graphs
24: Integrating products of quadratic forms
25: Sorting and Ranking of Self-Delimiting Numbers with Applications to Outerplanar Graph Isomorphism
26: The power of adaptivity in source identification with time queries on the path
27: An Upper Bound for Sorting $R_n$ with LRE
28: On the Fine-Grained Complexity of Parity Problems
29: Generating random bigraphs with preferential attachment
30: Coreset-based Strategies for Robust Center-type Problems
31: Connecting MapReduce Computations to Realistic Machine Models
32: Multistage s-t Path: Confronting Similarity with Dissimilarity
33: Manipulating Districts to Win Elections: Fine-Grained Complexity
34: An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling
35: Building large k-cores from sparse graphs
36: Compact Merkle Multiproofs
37: Distributed Maximum Matching Verification in CONGEST
38: How to Solve Fair $k$-Center in Massive Data Models
39: Computing the k Densest Subgraphs of a Graph
40: Dynamics of Cycles in Polyhedra I: The Isolation Lemma
41: Faster Algorithms for Orienteering and $k$-TSP
42: Fuzzy Simultaneous Congruences
43: Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem
44: An Efficient Framework for Balancing Submodularity and Cost
45: k-means++: few more steps yield constant approximation
46: Probabilistically Faulty Searching on a Half-Line
47: Polynomial Time Algorithms for Tracking Path Problems
48: Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model
49: Fair Clustering with Multiple Colors
50: Simplex based Steiner tree instances yield large integrality gaps for the bidirected cut relaxation
51: On the Planar Two-Center Problem and Circular Hulls
52: Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
53: Fast and linear-time string matching algorithms based on the distances of $q$-gram occurrences
54: Translating Between Wavelet Tree and Wavelet Matrix Construction
55: BB_Evac: Fast Location-Sensitive Behavior-Based Building Evacuation
56: Span Recovery for Deep Neural Networks with Applications to Input Obfuscation
57: Efficient Construction of Behavior Graphs for Uncertain Event Data
58: Subexponential parameterized algorithms and kernelization on almost chordal graphs
59: Massively Parallel Algorithms for Small Subgraph Counting
60: U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
61: Storage Space Allocation Strategy for Digital Data with Message Importance
62: Online Policies for Efficient Volunteer Crowdsourcing
63: Fast Multi-Subset Transform and Weighted Sums Over Acyclic Digraphs
64: Eccentricity terrain of $\delta$-hyperbolic graphs
65: Space Efficient Deterministic Approximation of String Measures
66: Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
67: Quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
68: Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities
69: Reliable Distributed Clustering with Redundant Data Assignment
70: Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs
71: A general kernelization technique for domination and independence problems in sparse classes
72: Compressed Data Structures for Binary Relations in Practice
73: Incremental Sampling Without Replacement for Sequence Models
74: A polynomial lower bound on adaptive complexity of submodular maximization
75: A symmetric alternating minimization algorithm for total variation minimization
76: Practical Estimation of Renyi Entropy