# Item

ITEM ACTIONSEXPORT

Released

Report

#### Realizing degree sequences in parallel

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-94-122.pdf

(Any fulltext), 200KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Arikati, S., & Maheshwari, A.(1994). *Realizing degree sequences
in parallel* (MPI-I-1994-122). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B69C-7

##### Abstract

A sequence $d$ 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$. The graph $G$ is said to be a
realization of $d$. We provide an efficient
parallel algorithm to realize $d$.
Before our result, it was not known if the problem of
realizing $d$ is in $NC$.