Finding a \(\Delta\)-regular supergraph of minimum order (Q1408809)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding a \(\Delta\)-regular supergraph of minimum order |
scientific article |
Statements
Finding a \(\Delta\)-regular supergraph of minimum order (English)
0 references
25 September 2003
0 references
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.
0 references
regular supergraphs
0 references
regularizable
0 references