Buchumschlag

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ferber, Asaf, Hardiman, Liam, Chen, Xiaonan
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Connectivity Labeling in Faulty Colored Graphs
von: Petruschka, Asaf, et al.
Veröffentlicht: (2024)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
von: Bansal, Nikhil, et al.
Veröffentlicht: (2026)

Simple and Optimal Sublinear Algorithms for Mean Estimation
von: Bertolotti, Beatrice, et al.
Veröffentlicht: (2024)

Sublinear Algorithms for TSP via Path Covers
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2023)

Sublinear Space Graph Algorithms in the Continual Release Model
von: Epasto, Alessandro, et al.
Veröffentlicht: (2024)

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs
von: Peng, Pan, et al.
Veröffentlicht: (2025)

Sublinear Random Access Generators for Preferential Attachment Graphs
von: Even, Guy, et al.
Veröffentlicht: (2016)

Improved Sublinear-time Moment Estimation using Weighted Sampling
von: Bhattacharya, Anup, et al.
Veröffentlicht: (2025)

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
von: Chen, Yixin, et al.
Veröffentlicht: (2025)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
von: Parter, Merav, et al.
Veröffentlicht: (2025)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
von: Roditty, Liam, et al.
Veröffentlicht: (2025)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2024)

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
von: Biedl, Therese, et al.
Veröffentlicht: (2026)

Sublinear Time Quantum Algorithm for Attention Approximation
von: Song, Zhao, et al.
Veröffentlicht: (2026)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2026)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
von: Parter, Merav, et al.
Veröffentlicht: (2024)

Computing String Covers in Sublinear Time
von: Radoszewski, Jakub, et al.
Veröffentlicht: (2024)

On Solving Linear Systems in Sublinear Time
von: Andoni, Alexandr, et al.
Veröffentlicht: (2018)

Almost-Optimal Sublinear Additive Spanners
von: Tan, Zihan, et al.
Veröffentlicht: (2023)

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
von: Aggarwal, Divesh, et al.
Veröffentlicht: (2020)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
von: Hu, Hang, et al.
Veröffentlicht: (2022)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
von: Moroie, Gregory
Veröffentlicht: (2025)

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
von: Chen, Xi, et al.
Veröffentlicht: (2024)

Solving the Correlation Cluster LP in Sublinear Time
von: Cao, Nairen, et al.
Veröffentlicht: (2025)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
von: He, Jialin, et al.
Veröffentlicht: (2025)

Counting Distinct Square Substrings in Sublinear Time
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2025)

Sublinear Spectral Clustering Oracle with Little Memory
von: Shen, Ranran, et al.
Veröffentlicht: (2026)

Improved Algorithms for Effective Resistance Computation on Graphs
von: Yang, Yichun, et al.
Veröffentlicht: (2025)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
von: Kadria, Avi, et al.
Veröffentlicht: (2025)

Fault-Equivalent Lowest Common Ancestors
von: Petruschka, Asaf
Veröffentlicht: (2024)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
von: Dai, Jiangqi, et al.
Veröffentlicht: (2025)

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
von: Eden, Talya, et al.
Veröffentlicht: (2025)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
von: Goranci, Gramoz, et al.
Veröffentlicht: (2023)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
von: Kempa, Dominik, et al.
Veröffentlicht: (2024)

Improved Streaming Edge Coloring
von: Chechik, Shiri, et al.
Veröffentlicht: (2025)

A Near-Real-Time Reduction-Based Algorithm for Coloring Massive Graphs
von: Zhu, Chenghao, et al.
Veröffentlicht: (2025)

Sublinear Metric Steiner Forest via Maximal Independent Set
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2025)