MPI-INF/SWS Research Reports 1991-2021
2. Number - only D1
MPI-I-94-122
Realizing degree sequences in parallel
Arikati, Srinivasa R. and Maheshwari, Anil
April 1994, 27 pages.
.Status: available - back from printing
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$.
-
MPI-I-94-122.pdf
- Attachement: MPI-I-94-122.dvi.gz (49 KBytes); MPI-I-94-122.pdf (199 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-122
BibTeX@TECHREPORT{ArikatiMaheshwari94,
AUTHOR = {Arikati, Srinivasa R. and Maheshwari, Anil},
TITLE = {Realizing degree sequences in parallel},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-94-122},
MONTH = {April},
YEAR = {1994},
ISSN = {0946-011X},
}