.png){kind=icon}
.png){kind=icon}
Return
Directed hypergraph connectivity augmentation by hyperarc reorientations
.png){kind=icon}
PRE
AI
DOI：10.1016/j.dam.2026.04.035.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The orientation theorem of Nash-Williams states that an undirected graph admits a k-arc-connected orientation if and only if it is 2k-edge-connected. Recently, Ito et al. showed that any orientation of an undirected 2k-edge-connected graph can be transformed into a k-arc-connected orientation by reorienting one arc at a time without decreasing the arc-connectivity at any step, thus providing an algorithmic proof of Nash-Williams' theorem. We generalize their result to hypergraphs and therefore provide an algorithmic proof of the characterization of hypergraphs with a k-hyperarc-connected orientation originally given by Frank et al. We prove that any orientation of an undirected (k, k)-partition-connected hypergraph can be transformed into a k-hyperarc-connected orientation by reorienting one hyperarc at a time without decreasing the hyperarc-connectivity in any step. Furthermore, we provide a simple combinatorial algorithm for computing such a transformation in polynomial time. Our result is a new polynomial algorithm for computing a k-hyperarc-connected orientation of a hypergraph if one exists. (c) 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Keywords:
Hypergraph
Connectivity
Orientation
Algorithms
Journal
D
IF:
1.1
Papers:
336
Citations:
7.7K