Cover Image

Hypergraph Connectivity Augmentation in Strongly Polynomial Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bérczi, Kristóf, Chandrasekaran, Karthekeyan, Király, Tamás, Kulkarni, Shubhang
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Splitting-off in Hypergraphs
by: Bérczi, Kristóf, et al.
Published: (2023)

Hypergraph Splitting-Off via Element-Connectivity Preserving Reductions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Approximating Submodular Matroid-Constrained Partitioning
by: Bérczi, Kristóf, et al.
Published: (2025)

Rainbow Arborescence Conjecture
by: Bérczi, Kristóf, et al.
Published: (2024)

Approximating maximum-size properly colored forests
by: Bai, Yuhang, et al.
Published: (2024)

$\{s,t\}$-Separating Principal Partition Sequence of Submodular Functions
by: Bérczi, Kristóf, et al.
Published: (2025)

Inverse matroid optimization under subset constraints
by: Bérczi, Kristóf, et al.
Published: (2025)

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
by: German, Samuel
Published: (2026)

A Tale of Santa Claus, Hypergraphs and Matroids
by: Davies, Sami, et al.
Published: (2018)

Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
by: Jordon, Addie, et al.
Published: (2025)

Fanciful Figurines flip Free Flood-It -- Polynomial-Time Miniature Painting on Co-gem-free Graphs
by: Rosenke, Christian, et al.
Published: (2026)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
by: Shao, Shuai, et al.
Published: (2023)

Sampling Balanced Forests of Grids in Polynomial Time
by: Cannon, Sarah, et al.
Published: (2023)

Polynomial Kernels for Spanning Tree with Diversity Requirements
by: Golovach, Petr A., et al.
Published: (2026)

An Enumerative Perspective on Connectivity
by: Akmal, Shyan
Published: (2023)

Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences
by: Mihalák, Matúš, et al.
Published: (2015)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
by: Bourneuf, Romain, et al.
Published: (2025)

Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
by: Brosse, Caroline, et al.
Published: (2024)

Optimal and Efficient Partite Decompositions of Hypergraphs
by: Krapivin, Andrew, et al.
Published: (2025)

On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2023)

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
by: Foucaud, Florent, et al.
Published: (2025)

Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
by: Bartier, Valentin, et al.
Published: (2023)

Polynomial-Time Pseudodeterministic Construction of Primes
by: Chen, Lijie, et al.
Published: (2023)

Multiway Cuts with a Choice of Representatives
by: Bérczi, Kristóf, et al.
Published: (2024)

The Strong Birthday Problem Revisited
by: Tripathy, Chijul B.
Published: (2025)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
by: Bedert, Benjamin, et al.
Published: (2025)

Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
by: Chandrasekaran, Karthekeyan, et al.
Published: (2023)

Problems on Group-labeled Matroid Bases
by: Hörsch, Florian, et al.
Published: (2024)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

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

DRESS and the WL Hierarchy: Climbing One Deletion at a Time
by: Velilla, Eduar Castrillo
Published: (2026)

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

Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
by: Soulignac, Francisco J.
Published: (2025)

The parameterized complexity of Strong Conflict-Free Vertex-Connection Colorability
by: Feghali, Carl, et al.
Published: (2025)

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

Determining Implication of Fixed Matrix Prenex Normal Forms Can Be Decided in Linear Time
by: Wang, Adam
Published: (2025)

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
by: Crane, Alex, et al.
Published: (2025)

Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)