2020/10/20 by Zschoche, Philipp
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2010.10408
A temporal graph is a sequence of graphs (called layers) over the same vertex set -- describing a graph topology which is subject to discrete changes over time. A Δ-temporal matching M is a set of time edges (e,t) (an edge e paired up with a point in time t) such that for all distinct time edges (e,t),(e',t') ∈ M we have that e and e' do not share an endpoint, or the time-labels t and t' are at least Δ time units apart. Mertzios et al. [STACS '20] provided a 2O(Δν)⋅ |\mathcal G|O(1)-time algorithm to compute the maximum size of a Δ-temporal matching in a temporal graph \mathcal G, where |\mathcal G| denotes the size of \mathcal G, and ν is the Δ-vertex cover number of \mathcal G. The Δ-vertex cover number is the minimum number ν such that the classical vertex cover number of the union of any Δ consecutive layers of the temporal graph is upper-bounded by ν. We show an improved algorithm to compute a Δ-temporal matching of maximum size with a running time of ΔO(ν)⋅ |\mathcal G| and hence provide an exponential speedup in terms of Δ.