A sequence d = (d1, d2, …, dn) of integers is a degree sequence if there exists a (simple) graph G such that the components of d are equal to the degrees of the vertices of G. We present an O(n)-time sequential algorithm to realize d, i.e., to compute the graph G. We provide an efficient parallel implementation of our algorithm.

Additional Metadata
Series Lecture Notes in Computer Science
Citation
Arikati, S.R. (Srinivasa Rao), & Maheshwari, A. (1994). An O(n) algorithm for realizing degree sequences. In Lecture Notes in Computer Science.