Packing directed Hamilton cycles online

DOI10.1137/17M1112273MaRDI QIDQ3174695zbMATH OpenWikidataFDO

Authors Michael Anastos, Joseph Briggs

Publication date 18 July 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.01965

zbMATH Keywords

Hamilton cyclesonline algorithmspacking

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80)

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 w.h.p.@ the first digraph in this process with both in-degree and out-degree $geqq$ 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 emph{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 of the process that contains $q$ disjoint Hamilton cycles.

Recommendations

• Packing Hamilton cycles online
• Getting a directed Hamilton cycle two times faster
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs

Cites work

• An algorithm for finding hamilton cycles in random directed graphs
• Clutter percolation and random graphs
• Edge-disjoint Hamilton cycles in random graphs
• Getting a directed Hamilton cycle two times faster
• Hamiltonian circuits in random graphs
• Hamiltonicity thresholds in Achlioptas processes
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• scientific article; zbMATH DE number 3950585 (Why is no real title available?)
• scientific article; zbMATH DE number 3549021 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs
• On the strength of connectedness of a random graph
• Optimal packings of Hamilton cycles in sparse random graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Rainbow Hamilton cycles in random graphs
• Rainbow Hamilton cycles in random graphs and hypergraphs
• The fundamental limit theorems in probability

Cited in

(4)

• Getting a directed Hamilton cycle two times faster
• Pattern colored Hamilton cycles in random graphs
• Packing Hamilton cycles online
• Packing directed cycles efficiently

This page was built for publication: Packing directed Hamilton cycles online

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174695)