Buchumschlag

A characterization of one-sided error testable graph properties in bounded degeneracy graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Lachish, Oded, Levi, Amit, Newman, Ilan, Reidl, Felix
Format:	Preprint
Veröffentlicht:	2026
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

A sufficient condition for characterizing the one-sided testable properties of families of graphs in the Random Neighbour Oracle Model
von: Awofeso, Christine, et al.
Veröffentlicht: (2025)

Counting large patterns in degenerate graphs
von: Awofeso, Christine, et al.
Veröffentlicht: (2025)

A practical algorithm for 3-admissibility
von: Awofeso, Christine, et al.
Veröffentlicht: (2025)

Efficient Trace Frequency Queries in Sparse Graphs
von: Awofeso, Christine, et al.
Veröffentlicht: (2025)

A practical algorithm for 2-admissibility
von: Awofeso, Christine, et al.
Veröffentlicht: (2025)

A characterization of testable hypergraph properties
von: Joos, Felix, et al.
Veröffentlicht: (2017)

Minimizers in Semi-Dynamic Strings
von: Zuba, Wiktor, et al.
Veröffentlicht: (2025)

Testing $C_k$-freeness in bounded-arboricity graphs
von: Eden, Talya, et al.
Veröffentlicht: (2024)

Holey graphs: very large Betti numbers are testable
von: Szabó, Dániel, et al.
Veröffentlicht: (2024)

DNF formulas are efficiently testable with relative error
von: Chen, Xi, et al.
Veröffentlicht: (2026)

Testing Quasiperiodicity
von: Awofeso, Christine, et al.
Veröffentlicht: (2025)

Upper bounds on the theta function of random graphs
von: Feige, Uriel, et al.
Veröffentlicht: (2025)

The Leafed Induced Subtree in chordal and bounded treewidth graphs
von: Baste, Julien
Veröffentlicht: (2023)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
von: Adar, Tomer, et al.
Veröffentlicht: (2026)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2025)

Faster diameter computation in graphs of bounded Euler genus
von: Kluk, Kacper, et al.
Veröffentlicht: (2025)

Coloring tournaments with few colors: Algorithms and complexity
von: Klingelhoefer, Felix, et al.
Veröffentlicht: (2023)

Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
von: Adar, Tomer, et al.
Veröffentlicht: (2026)

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
von: Adar, Tomer, et al.
Veröffentlicht: (2024)

Support Testing in the Huge Object Model
von: Adar, Tomer, et al.
Veröffentlicht: (2023)

Optimal mass estimation in the conditional sampling model
von: Adar, Tomer, et al.
Veröffentlicht: (2025)

Testing H-freeness on sparse graphs, the case of bounded expansion
von: Humeau, Samuel, et al.
Veröffentlicht: (2025)

Lower bounds for graph reconstruction with maximal independent set queries
von: Michel, Lukas, et al.
Veröffentlicht: (2024)

Generalizing Roberts' characterization of unit interval graphs
von: Martínez, Virginia Ardévol, et al.
Veröffentlicht: (2024)

Packing $K_r$s in bounded degree graphs
von: McKay, Michael, et al.
Veröffentlicht: (2022)

Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
von: Paul-Pena, Daniel, et al.
Veröffentlicht: (2025)

Making an oriented graph acyclic using inversions of bounded or prescribed size
von: Bang-Jensen, Jørgen, et al.
Veröffentlicht: (2025)

A Space-Efficient Algebraic Approach to Robotic Motion Planning
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
von: Bencs, Ferenc, et al.
Veröffentlicht: (2025)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
von: Chudnovsky, Maria, et al.
Veröffentlicht: (2024)

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
von: Bonamy, Marthe, et al.
Veröffentlicht: (2022)

Circular-arc graphs and the Helly property
von: Derbisz, Jan, et al.
Veröffentlicht: (2024)

Differentially private graph coloring
von: Xie, Michael, et al.
Veröffentlicht: (2026)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
von: Kluk, Kacper, et al.
Veröffentlicht: (2025)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation
von: Schwartz, Oded, et al.
Veröffentlicht: (2025)

Testing Distributions of Huge Objects
von: Goldreich, Oded, et al.
Veröffentlicht: (2022)

Clique-free t-matchings in degree-bounded graphs
von: Paluch, Katarzyna, et al.
Veröffentlicht: (2024)

The trace reconstruction problem for spider graphs
von: Sun, Alec, et al.
Veröffentlicht: (2022)