Imagen de Portada

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Großmann, Ernestine, Schulz, Christian, Strash, Darren, Wagner, Antonie
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

Engineering Data Reduction for Nested Dissection
por: Ost, Lara, et al.
Publicado: (2020)

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

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

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

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

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

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

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

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

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

Efficient Parallel Algorithms for Hypergraph Matching
por: Reinstädtler, Henrik, et al.
Publicado: (2026)

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

Semi-Streaming Algorithms for Hypergraph Matching
por: Reinstädtler, Henrik, et al.
Publicado: (2025)

Improved Certificates for Independence Number in Semirandom Hypergraphs
por: Kothari, Pravesh, et al.
Publicado: (2026)

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

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

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

On the Complexity of Bilevel Independent Set Problem
por: Muluk, Komal
Publicado: (2026)

A Tolerant Independent Set Tester
por: Seth, Cameron
Publicado: (2025)

Half-Approximating Maximum Dicut in the Streaming Setting
por: Azarmehr, Amir, et al.
Publicado: (2025)

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

Online Maximum Independent Set of Hyperrectangles
por: Advani, Rishi, et al.
Publicado: (2023)

From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
por: Dadush, Daniel, et al.
Publicado: (2025)

Independent Sets in Hypergraphs
por: Jacques Verstraete, et al.
Publicado: (2026)

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

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
por: Bérczi, Kristóf, et al.
Publicado: (2024)

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

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

Two New Upper Bounds for the Maximum k-plex Problem
por: Zheng, Jiongzhi, et al.
Publicado: (2023)

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

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

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

Revisiting a Successful Reduction Rule for Dominating Set
por: Geis, Lukas, et al.
Publicado: (2025)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
por: Cohen-Addad, Vincent, et al.
Publicado: (2025)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
por: Dhawan, Abhishek, et al.
Publicado: (2026)

A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
por: Zhou, Yi, et al.
Publicado: (2025)