אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

In the Degree Realization problem with respect to a family P of graphs the input is a non-increasing sequence d = (d1, . . . , dn) of positive integers, and the goal is to decide whether there exists a simple undirected graph G ∈ P, whose degrees correspond to d, i.e., such that deg(G) = d. In this paper we consider the version of Degree Realization in which the realization is required to be a forest (i.e., P is the family for forests). We consider optimized Degree Realization in which the goal is to obtain a realization that minimizes an objective function f. That is, the goal is to find a realization G that minimizes f(G) among the realizations of the given input sequence. More specifically, we focus on the following functions: the size of an optimal vertex cover and the size of an optimal dominating set. We also consider the total and paired versions of both Min Vertex Cover and Min Dominating Set. We provide characterizations and linear time realization algorithms for all the above-mentioned problems.