An O(n) algorithm for realizing degree sequences
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.
|Series||Lecture Notes in Computer Science|
Arikati, S.R. (Srinivasa Rao), & Maheshwari, A. (1994). An O(n) algorithm for realizing degree sequences. In Lecture Notes in Computer Science.