Image de couverture de livre

Testing $C_k$-freeness in bounded-arboricity graphs

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Eden, Talya, Levi, Reut, Ron, Dana
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
par: Eden, Talya, et autres
Publié: (2025)

A note on approximating the average degree of bounded arboricity graphs
par: Eden, Talya, et autres
Publié: (2026)

Testing H-freeness on sparse graphs, the case of bounded expansion
par: Humeau, Samuel, et autres
Publié: (2025)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
par: Eden, Talya, et autres
Publié: (2025)

Testing Distributions of Huge Objects
par: Goldreich, Oded, et autres
Publié: (2022)

Bicriteria approximation for $k$-edge-connectivity
par: Nutov, Zeev, et autres
Publié: (2025)

Characterizing and Testing Configuration Stability in Two-Dimensional Threshold Cellular Automata
par: Nakar, Yonatan, et autres
Publié: (2025)

Sublinear Random Access Generators for Preferential Attachment Graphs
par: Even, Guy, et autres
Publié: (2016)

A characterization of one-sided error testable graph properties in bounded degeneracy graphs
par: Lachish, Oded, et autres
Publié: (2026)

Fast Agnostic Learners in the Plane
par: Eden, Talya, et autres
Publié: (2025)

Triangle Counting with Local Edge Differential Privacy
par: Eden, Talya, et autres
Publié: (2023)

On $k$-connectivity oracles in $k$-connected graphs
par: Nutov, Zeev
Publié: (2026)

Dynamic O(arboricity) coloring in polylogarithmic worst-case time
par: Ghaffari, Mohsen, et autres
Publié: (2024)

Support Testing in the Huge Object Model
par: Adar, Tomer, et autres
Publié: (2023)

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
par: Adar, Tomer, et autres
Publié: (2024)

Upper bounds on the theta function of random graphs
par: Feige, Uriel, et autres
Publié: (2025)

Distributionally Robust $k$-of-$n$ Sequential Testing
par: Tan, Rayen, et autres
Publié: (2026)

The Leafed Induced Subtree in chordal and bounded treewidth graphs
par: Baste, Julien
Publié: (2023)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
par: Bodlaender, Hans L., et autres
Publié: (2025)

Improved fixed-parameter bounds for Min-Sum-Radii and Diameters $k$-clustering and their fair variants
par: Banerjee, Sandip, et autres
Publié: (2025)

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
par: Chakraborty, Sourav, et autres
Publié: (2024)

Sub-$n^k$ Deterministic algorithm for minimum $k$-way cut in simple graphs
par: Daga, Mohit
Publié: (2025)

A Sublinear Algorithm for Approximate Shortest Paths in Large Networks
par: Basu, Sabyasachi, et autres
Publié: (2024)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
par: Black, Hadley
Publié: (2023)

Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
par: An, Shinwoo, et autres
Publié: (2024)

Interactive Coding with Unbounded Noise
par: Fargion, Eden, et autres
Publié: (2024)

Faster diameter computation in graphs of bounded Euler genus
par: Kluk, Kacper, et autres
Publié: (2025)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
par: Adar, Tomer, et autres
Publié: (2026)

Dynamic algorithms for k-center on graphs
par: Cruciani, Emilio, et autres
Publié: (2023)

Lower bounds for graph reconstruction with maximal independent set queries
par: Michel, Lukas, et autres
Publié: (2024)

Envy-freeness in 3D Hedonic Games
par: McKay, Michael, et autres
Publié: (2022)

Expanderizing Higher Order Random Walks
par: Alev, Vedat Levi, et autres
Publié: (2024)

Making an oriented graph acyclic using inversions of bounded or prescribed size
par: Bang-Jensen, Jørgen, et autres
Publié: (2025)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
par: Censor-Hillel, Keren, et autres
Publié: (2025)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
par: Chudnovsky, Maria, et autres
Publié: (2024)

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
par: Bonamy, Marthe, et autres
Publié: (2022)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
par: Adar, Tomer, et autres
Publié: (2026)

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
par: Ma, Will, et autres
Publié: (2019)

Optimal mass estimation in the conditional sampling model
par: Adar, Tomer, et autres
Publié: (2025)

Packing $K_r$s in bounded degree graphs
par: McKay, Michael, et autres
Publié: (2022)