Finding a \(\Delta\)-regular supergraph of minimum order (Q1408809)

Since various algorithmic graph problems can be reduced to the case of regular graphs, there is a motivation for constructing a regular supergraph for a given non-regular graph efficiently. In this note the authors show that, given a graph of maximum degree \(\Delta\), a \(\Delta\)-supergraph of it of minimum order can be computed in \(O(\min\{\Delta^{1,5}|V|^{2,5}, \Delta^6+ \Delta|V|\})\) time.