Two spanning temporal arborescences under half-connectivity
Two spanning temporal arborescences under half-connectivity
Let be an acyclic temporal network on vertices. For vertices , let denote the maximum number of arc-disjoint -respecting -paths, and let a spanning -respecting -arborescence be a spanning arborescence rooted at whose root-to-vertex paths respect the temporal ordering.
Two-arborescence conjecture. If
for every , then contains a packing of spanning -respecting -arborescences.
This would improve the preceding sufficient condition for packing two spanning temporal arborescences. The conjecture is presented as an open strengthening for acyclic temporal networks; no resolution is given here.
Sources & referencesView supporting material
Primary source
Romain Chapoullié and Zoltán Szigeti, “On packing time-respecting arborescences”, arXiv:2203.01096 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.