Back to Search
Start Over
PACKING DIRECTED HAMILTON CYCLES ONLINE.
- Source :
-
SIAM Journal on Discrete Mathematics . 2018, Vol. 32 Issue 2, p1505-1539. 35p. - Publication Year :
- 2018
-
Abstract
- Consider a directed analogue of the random graph process on n vertices, where the n(n - 1) edges are ordered uniformly at random and revealed one at a time. It is known that with high probability (w.h.p.) the first digraph in this process with both in-degree and out-degree ≥ q has a q-edge-coloring with a Hamilton cycle in each color. We show that this coloring can be constructed online, where each edge must be irrevocably colored as soon as it appears. In a similar fashion, for the undirected random graph process, we present an online n-edge-coloring algorithm which yields w.h.p. q disjoint rainbow Hamilton cycles in the first graph containing q disjoint Hamilton cycles. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 32
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 130882826
- Full Text :
- https://doi.org/10.1137/17M1112273