An O(n-log-log-n) Time Algorithm for Constructing a Graph of Maximum Connectivity with Prescribed Degrees

摘要

A sequence of nonnegative integers D = (d1, d2, ..., dn) is graphical if there is a graph with degree sequence D. The connectivity κ(D) of a graphical sequence D is defined to be the maximum integer k such that there is a k-connected graph with degree sequence D. In this paper, we present an O(n log log n) time algorithm, for a given graphical sequence D, to construct a κ(D)-connected graph with degree sequence D.