:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Seth, Cameron
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2503.21441
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Near-Optimal Property Testers for Pattern Matching
by: Jin, Ce, et al.
Published: (2025)

New Graph and Hypergraph Container Lemmas with Applications in Property Testing
by: Blais, Eric, et al.
Published: (2024)

Testing Graph Properties with the Container Method
by: Blais, Eric, et al.
Published: (2023)

On the Structure of Replicable Hypothesis Testers
by: Aamand, Anders, et al.
Published: (2025)

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

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
by: Saito, Rin, et al.
Published: (2025)

Optimal Neighborhood Exploration for Dynamic Independent Sets
by: Borowitz, Jannick, et al.
Published: (2024)

Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
by: Cardinal, Jean, et al.
Published: (2026)

Fault-Tolerant Approximate Distance Oracles with a Source Set
by: Dey, Dipan, et al.
Published: (2025)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Finding Triangles or Independent Sets; and Other Dual Pair Approximations
by: Dumitrescu, Adrian
Published: (2021)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
by: Großmann, Ernestine, et al.
Published: (2026)

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
by: Großmann, Ernestine, et al.
Published: (2024)

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
by: Eiben, Eduard, et al.
Published: (2024)

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

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

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
by: Ghoshal, Suprovat, et al.
Published: (2026)

Online Algorithms for Geometric Independent Set
by: De, Minati, et al.
Published: (2026)

On the Complexity of Bilevel Independent Set Problem
by: Muluk, Komal
Published: (2026)

Rounding Large Independent Sets on Expanders
by: Bafna, Mitali, et al.
Published: (2024)

Learning-augmented Maximum Independent Set
by: Braverman, Vladimir, et al.
Published: (2024)

A Distributed Conductance Tester Without Global Information Collection
by: Batu, Tugkan, et al.
Published: (2023)

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

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
by: Chaplick, Steven, et al.
Published: (2024)

Deterministic Independent Sets in the Semi-Streaming Model
by: Ye, Daniel
Published: (2025)

Stable Approximation Algorithms for Dominating Set and Independent Set
by: de Berg, Mark, et al.
Published: (2024)

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
by: Kobayashi, Yasuaki, et al.
Published: (2023)

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
by: Marin, Malory
Published: (2025)

Max Weight Independent Set in sparse graphs with no long claws
by: Abrishami, Tara, et al.
Published: (2023)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

Tolerant Testing for Unique Games
by: Yoshida, Yuichi
Published: (2026)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
by: Efthymiou, Charilaos, et al.
Published: (2023)

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2026)

Fault-Tolerant ST-Diameter Oracles
by: Bilò, Davide, et al.
Published: (2023)

Fault-Tolerant Bounded Flow Preservers
by: Bansal, Shivam, et al.
Published: (2024)

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
by: Fahrbach, Matthew, et al.
Published: (2024)

Pairwise-Independent Contention Resolution
by: Gupta, Anupam, et al.
Published: (2024)

History-Independent Load Balancing
by: Bender, Michael A., et al.
Published: (2026)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
by: Kosinas, Evangelos
Published: (2025)