1994-01-01
An O(n) algorithm for realizing degree sequences
Publication
Publication
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.
|