Cover Image

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kumar, Akash, Lahiri, Abhiruk, Seshadhri, C.
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
by: Beretta, Lorenzo, et al.
Published: (2025)

The complexity of testing all properties of planar graphs, and the role of isomorphism
by: Basu, Sabyasachi, et al.
Published: (2021)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2024)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2022)

Approximating Fair $k$-Min-Sum-Radii in Euclidean Space
by: Drexler, Lukas, et al.
Published: (2023)

Parameterized Shortest Path Reconfiguration
by: Bousquet, Nicolas, et al.
Published: (2024)

A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids
by: Black, Hadley, et al.
Published: (2023)

Multiplicative Spanners in Minor-Free Graphs
by: Bodwin, Greg, et al.
Published: (2025)

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

Separator Theorem for Minor-Free Graphs in Linear Time
by: Bonnet, Édouard, et al.
Published: (2025)

A Separator for Minor-Free Graphs Beyond the Flow Barrier
by: Le, Hung
Published: (2026)

Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
by: Paul-Pena, Daniel, et al.
Published: (2025)

Counting Patterns in Degenerate Graphs in Constant Space
by: Komarath, Balagopal, et al.
Published: (2025)

Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
by: Chakrabarty, Deeparnab, et al.
Published: (2024)

Graph Reconstruction with a Connected Components Oracle
by: Harviainen, Juha, et al.
Published: (2025)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
by: Yoshida, Yuichi
Published: (2026)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
by: Neiman, Ofer, et al.
Published: (2026)

Graph Partitioning With Limited Moves
by: Behbahani, Majid, et al.
Published: (2024)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
by: Ahi, Mridul, et al.
Published: (2025)

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
by: Manoharan, Vignesh, et al.
Published: (2025)

How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
by: Conroy, Jonathan, et al.
Published: (2025)

A note on approximating the average degree of bounded arboricity graphs
by: Eden, Talya, et al.
Published: (2026)

Estimating Diffusion Degree on Graph Streams
by: Gore, Vinit Ramesh, et al.
Published: (2024)

Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model
by: Räcke, Harald, et al.
Published: (2024)

Tera-Scale Multilevel Graph Partitioning
by: Salwasser, Daniel, et al.
Published: (2024)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
by: Kothari, Pravesh, et al.
Published: (2024)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
by: Kapralov, Michael, et al.
Published: (2022)

Improved Massively Parallel Triangle Counting in $O(1)$ Rounds
by: Liu, Quanquan C., et al.
Published: (2024)

Partitioning Trillion Edge Graphs on Edge Devices
by: Chhabra, Adil, et al.
Published: (2024)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
by: Das, Syamantak, et al.
Published: (2024)

Hamming Distance Oracle
by: Boneh, Itai, et al.
Published: (2024)

Realization of Temporally Connected Graphs Based on Degree Sequences
by: Casteigts, Arnaud, et al.
Published: (2025)

Contiguous Graph Partitioning For Optimal Total Or Bottleneck Communication
by: Ahrens, Willow
Published: (2020)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
by: Marx, Dániel, et al.
Published: (2026)

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
by: Parter, Merav, et al.
Published: (2024)

Hyper-distance Oracles in Hypergraphs
by: Preti, Giulia, et al.
Published: (2023)

Distributed Distance Sensitivity Oracles
by: Manoharan, Vignesh, et al.
Published: (2024)

Distance Approximating Minors for Planar and Minor-Free Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Linear-Time Multilevel Graph Partitioning via Edge Sparsification
by: Gottesbüren, Lars, et al.
Published: (2025)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)