Cover Image

A sufficient condition for characterizing the one-sided testable properties of families of graphs in the Random Neighbour Oracle Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Awofeso, Christine, Greaves, Patrick, Lachish, Oded, Levi, Amit, Reidl, Felix
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Counting large patterns in degenerate graphs
by: Awofeso, Christine, et al.
Published: (2025)

A characterization of one-sided error testable graph properties in bounded degeneracy graphs
by: Lachish, Oded, et al.
Published: (2026)

A practical algorithm for 2-admissibility
by: Awofeso, Christine, et al.
Published: (2025)

A practical algorithm for 3-admissibility
by: Awofeso, Christine, et al.
Published: (2025)

Efficient Trace Frequency Queries in Sparse Graphs
by: Awofeso, Christine, et al.
Published: (2025)

Testing Quasiperiodicity
by: Awofeso, Christine, et al.
Published: (2025)

A characterization of testable hypergraph properties
by: Joos, Felix, et al.
Published: (2017)

Minimizers in Semi-Dynamic Strings
by: Zuba, Wiktor, et al.
Published: (2025)

Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams
by: Chakrabarti, Amit, et al.
Published: (2024)

Optimal mass estimation in the conditional sampling model
by: Adar, Tomer, et al.
Published: (2025)

Random Schreier graphs as expanders
by: Caillat-Grenier, Geoffroy
Published: (2023)

Holey graphs: very large Betti numbers are testable
by: Szabó, Dániel, et al.
Published: (2024)

Posets are easily testable
by: Fekete, Panna Tímea, et al.
Published: (2023)

Better coloring of 3-colorable graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2024)

Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
by: Hommelsheim, Felix, et al.
Published: (2025)

Correlation Clustering with Vertex Splitting
by: Bentert, Matthias, et al.
Published: (2024)

Low-degree spanning trees of $2$-edge-connected graphs in linear time
by: Dereniowski, Dariusz, et al.
Published: (2024)

Splittable Spanning Trees and Balanced Forests in Dense Random Graphs
by: Gillman, David, et al.
Published: (2025)

DNF formulas are efficiently testable with relative error
by: Chen, Xi, et al.
Published: (2026)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

The Pareto Frontier of Randomized Learning-Augmented Online Bidding
by: Degryse, Mathis, et al.
Published: (2026)

A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures
by: Gudmundsson, Joachim, et al.
Published: (2021)

Realizing temporal graphs from fastest travel times
by: Klobas, Nina, et al.
Published: (2023)

A polynomial-time algorithm for recognizing high-bandwidth graphs
by: Varona, Luis M. B.
Published: (2026)

Computing parameters that generalize interval graphs using restricted modular partitions
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)

Optimal distance query reconstruction for graphs without long induced cycles
by: Bastide, Paul, et al.
Published: (2023)

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
by: Kumar, Akash, et al.
Published: (2026)

Online Combinatorial Optimization with Graphical Dependencies
by: Gao, Zhimeng, et al.
Published: (2025)

Offline green bin packing and its constrained variant
by: Gong, Mingyang, et al.
Published: (2026)

Exploiting Low Scanwidth to Resolve Soft Polytomies
by: Bruchhold, Sebastian, et al.
Published: (2025)

Online computation of normalized substring complexity
by: Kucherov, Gregory, et al.
Published: (2025)

Approximation algorithms for scheduling with rejection in green manufacturing
by: Gong, Mingyang, et al.
Published: (2025)

The cost of cyclic permutations and remainder sums in the Euclidean algorithm
by: Blomer, Valentin, et al.
Published: (2026)

Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs
by: Mosenzon, Ron
Published: (2025)

A Faster Directed Single-Source Shortest Path Algorithm
by: Duan, Ran, et al.
Published: (2026)

Polytope Scheduling with Groups: Unified Models and Optimal Guarantees
by: Lindermayr, Alexander, et al.
Published: (2025)

Minimum Riesz s-Energy Subset Selection in Ordered Point Sets via Dynamic Programming
by: Emmerich, Michael
Published: (2025)

Connected Components in Linear Work and Near-Optimal Time
by: Farhadi, Alireza, et al.
Published: (2023)

Online $b$-Matching with Stochastic Rewards
by: Albers, Susanne, et al.
Published: (2024)

Hierarchical Exponential Search Via K-Spines
by: Dong, Bob
Published: (2025)