Data Structures and Algorithms

Authors and titles for cs.DS in Jul 2023

[1]  arXiv:2307.00115 [pdf, ps, other]

Title: A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut

Authors: Vladimir Kolmogorov

Comments: To appear in ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2024)

Subjects: Data Structures and Algorithms (cs.DS)

[2]  arXiv:2307.00147 [pdf, other]

Title: Maximal $k$-Edge-Connected Subgraphs in Almost-Linear Time for Small $k$

Authors: Thatchaphol Saranurak, Wuwei Yuan

Comments: Accepted to ESA 2023

Subjects: Data Structures and Algorithms (cs.DS)

[3]  arXiv:2307.00317 [pdf, ps, other]

Title: On Finding Constrained Independent Sets in Cycles

Authors: Ishay Haviv

Comments: 23 pages

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Combinatorics (math.CO)

[4]  arXiv:2307.00357 [pdf, other]

Title: Abstract Orientable Incidence Structure and Algorithms for Finite Bounded Acyclic Categories. II. Data Structure and Fundamental Operations

Authors: Yu-Wei Huang

Subjects: Data Structures and Algorithms (cs.DS); Algebraic Geometry (math.AG); Combinatorics (math.CO)

[5]  arXiv:2307.00362 [pdf, ps, other]

Title: Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves

Authors: Emmanuel Sam, Benjamin Bergougnoux, Petr A. Golovach, Nello Blaser

Comments: 16 pages, accepted for presentation at FCT 2023

Subjects: Data Structures and Algorithms (cs.DS)

[6]  arXiv:2307.00406 [pdf, other]

Title: Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard

Authors: Łukasz Kowalik, Alexandra Lassota, Konrad Majewski, Michał Pilipczuk, Marek Sokołowski

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

[7]  arXiv:2307.00474 [pdf, other]

Title: Moments, Random Walks, and Limits for Spectrum Approximation

Authors: Yujia Jin, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)

[8]  arXiv:2307.00530 [pdf, other]

Title: Massively Parallel Algorithms for the Stochastic Block Model

Authors: Zelin Li, Pan Peng, Xianbin Zhu

Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC)

[9]  arXiv:2307.00604 [pdf, other]

Title: Listing Small Minimal $s,t$-separators in FPT-Delay

Authors: Batya Kenig

Subjects: Data Structures and Algorithms (cs.DS); Databases (cs.DB)

[10]  arXiv:2307.00627 [pdf, other]

Title: New Bounds for Time-Dependent Scheduling with Uniform Deterioration

Authors: Angelos Gkikas, Dimitrios Letsios, Tomasz Radzik, Kathleen Steinhöfel

Subjects: Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)

[11]  arXiv:2307.00644 [pdf, other]

Title: What if we tried Less Power? -- Lessons from studying the power of choices in hashing-based data structures

Authors: Stefan Walzer

Comments: This article appeared in the algorithms column of the bulletin of the EATCS, Issue Number 140, June 2023

Subjects: Data Structures and Algorithms (cs.DS)

[12]  arXiv:2307.00786 [pdf, other]

Title: An FTP Algorithm for Temporal Graph Untangling

Authors: Riccardo Dondi, Manuel Lafond

Subjects: Data Structures and Algorithms (cs.DS); Social and Information Networks (cs.SI)

[13]  arXiv:2307.00949 [pdf, other]

Title: Greedy Minimum-Energy Scheduling

Authors: Gunther Bidlingmaier

Subjects: Data Structures and Algorithms (cs.DS)

[14]  arXiv:2307.00971 [pdf, other]

Title: New Prophet Inequalities via Poissonization and Sharding

Authors: Elfarouk Harb

Comments: 51 pages. Major rewrite, several new results/figures

Subjects: Data Structures and Algorithms (cs.DS)

[15]  arXiv:2307.00985 [pdf, ps, other]

Title: An embarrassingly parallel optimal-space cardinality estimation algorithm

Authors: Emin Karayel

Comments: Conference version to appear at the 27th International Conference on Randomization and Computation (RANDOM 2023)

Subjects: Data Structures and Algorithms (cs.DS)

[16]  arXiv:2307.00996 [pdf, other]

Title: Kernelizing Problems on Planar Graphs in Sublinear Space and Polynomial Time

Authors: Arindam Biswas, Johannes Meintrup

Subjects: Data Structures and Algorithms (cs.DS)

[17]  arXiv:2307.01178 [pdf, ps, other]

Title: Learning Mixtures of Gaussians Using the DDPM Objective

Authors: Kulin Shah, Sitan Chen, Adam Klivans

Comments: 48 pages

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Machine Learning (stat.ML)

[18]  arXiv:2307.01218 [pdf, ps, other]

Title: Effective Resistances in Non-Expander Graphs

Authors: Dongrun Cai, Xue Chen, Pan Peng

Subjects: Data Structures and Algorithms (cs.DS)

[19]  arXiv:2307.01285 [pdf, other]

Title: Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

Authors: Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, Erik Jan van Leeuwen

Comments: Conference version to appear at the European Symposium on Algorithms (ESA 2023)

Subjects: Data Structures and Algorithms (cs.DS)

[20]  arXiv:2307.01318 [pdf, other]

Title: A contraction-recursive algorithm for treewidth

Authors: Hisao Tamaki

Comments: 17 pages, 2 figures, submitted IPEC 2023

Subjects: Data Structures and Algorithms (cs.DS)

[21]  arXiv:2307.01341 [pdf, other]

Title: Polynomial-time Approximation of Independent Set Parameterized by Treewidth

Authors: Parinya Chalermsook, Fedor Fomin, Thekla Hamm, Tuukka Korhonen, Jesper Nederlof, Ly Orgo

Comments: To appear in the 31st Annual European Symposium on Algorithms (ESA 2023)

Subjects: Data Structures and Algorithms (cs.DS)

[22]  arXiv:2307.01412 [pdf, other]

Title: Constant-time edge label and leaf pointer maintenance on sliding suffix trees

Authors: Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai, Takuya Mieno

Subjects: Data Structures and Algorithms (cs.DS)

[23]  arXiv:2307.01415 [pdf, other]

Title: Matrix Multiplication Using Only Addition

Authors: Daniel Cussen, Jeffrey D. Ullman

Comments: 9 pages, 2 figures

Subjects: Data Structures and Algorithms (cs.DS)

[24]  arXiv:2307.01428 [pdf, other]

Title: Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets

Authors: Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Comments: This is an extended version of the paper "Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets" from MFCS 2016

Subjects: Data Structures and Algorithms (cs.DS); Formal Languages and Automata Theory (cs.FL)

[25]  arXiv:2307.01500 [pdf, other]

Title: An Optimal Multiple-Class Encoding Scheme for a Graph of Bounded Hadwiger Number

Authors: Hsueh-I Lu

Comments: 35 pages, 6 figures

Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)