Cover Image

Optimal Neighborhood Exploration for Dynamic Independent Sets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Borowitz, Jannick, Großmann, Ernestine, Schulz, Christian
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Finding Maximum Weight 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2025)

Scalable Algorithms for 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2023)

Distributed Reductions for the Maximum Weight Independent Set Problem
by: Borowitz, Jannick, et al.
Published: (2025)

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

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

Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms
by: Großmann, Ernestine, et al.
Published: (2024)

Engineering Hypergraph $b$-Matching Algorithms
by: Großmann, Ernestine, et al.
Published: (2024)

FLASH-TB: Integrating Arc-Flags and Trip-Based Public Transit Routing
by: Großmann, Ernestine, et al.
Published: (2023)

Engineering Weighted Connectivity Augmentation Algorithms
by: Faraj, Marcelo Fonseca, et al.
Published: (2024)

From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation
by: Großmann, Ernestine, et al.
Published: (2025)

Finding Maximum Weight 2‐Packing Sets on Arbitrary Graphs
by: Jannick Borowitz, et al.
Published: (2026)

A Tolerant Independent Set Tester
by: Seth, Cameron
Published: (2025)

Chasing Small Sets Optimally Against Adaptive Adversaries
by: Coester, Christian, et al.
Published: (2026)

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

Near-Optimal Minimum Cuts in Hypergraphs at Scale
by: Chhabra, Adil, et al.
Published: (2025)

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

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

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)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
by: Bukov, Anton, et al.
Published: (2023)

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

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)

Time-Optimal Construction of String Synchronizing Sets
by: Ellert, Jonas, et al.
Published: (2026)

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

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

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

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
by: Antoniadis, Antonios, et al.
Published: (2020)

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)

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)

Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem
by: Gao, Xuan-Zhao, et al.
Published: (2024)

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
by: Rohwedder, Lars, et al.
Published: (2024)

Stochastic Traveling Salesperson Problem with Neighborhoods for Object Detection
by: Peng, Cheng, et al.
Published: (2024)

Assigning Agents to Increase Network-Based Neighborhood Diversity
by: Qiu, Zirou, et al.
Published: (2023)

Parallel Batch-Dynamic Maximal Independent Set
by: Blelloch, Guy, et al.
Published: (2026)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
by: Jiang, Yonggang, et al.
Published: (2025)