Strong orientation of a connected graph for a crossing family
Abdi, Ahmad
; Dalirrooyfarda, Mahsa; and Neuwohner, Meike
(2025)
Strong orientation of a connected graph for a crossing family.
Operations Research Letters.
ISSN 0167-6377
(In press)
Given a connected graph G = (V,E) and a crossing family C over ground set V such that |δG(U)| ≥ 2 for every U ∈ C, we prove there exists a strong orientation of G for C, i.e., an orientation of G such that each set in C has at least one outgoing and at least one incoming arc. This implies the main conjecture in Chudnovsky et al. (Disjoint dijoins. Journal of Combinatorial Theory, Series B, 120:18–35, 2016).
| Item Type | Article |
|---|---|
| Keywords | strongly connected orientation,crossing family,submodular flow,generalized set covering,total dual integrality,min-max theorem |
| Departments | Mathematics |
| Date Deposited | 08 Apr 2025 14:09 |
| Acceptance Date | 2025-02-20 |
| URI | https://researchonline.lse.ac.uk/id/eprint/127859 |
ORCID: https://orcid.org/0000-0002-3008-4167
ORCID: https://orcid.org/0000-0002-3664-3687
