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. |