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