Parallel algorithms for ranking of trees

Y. Liang; S. K. Dhall; S. Lakshmivarahan

doi:10.1109/SPDP.1990.143502

Parallel algorithms for ranking of trees

Y. Liang, S. K. Dhall, S. Lakshmivarahan

Computer Science

University of Oklahoma

Research output: Contribution to book or proceeding › Conference article › peer-review

3 Scopus citations

Abstract

Ranking a tree is defined as a mapping rho of the nodes to the set (1, 2,...) such that if there is a path from u to v and rho (u)= rho (v) then there is a node w on the path from u to v such that rho (w)> rho (u). The highest number assigned to the node is called the rank number of the mapping. A mapping rho with the smallest rank number is called optimal ranking. The best known serial algorithm takes O(n) time for the optimal node ranking. However, the problem of finding the optimal tree ranking appears to be highly sequential. It remains open whether it is in NC. The paper proposes a fast parallel algorithm for finding approximate optimal node ranking of trees using O(logn) steps with n² processors on a CRCW PRAM and an efficient parallel algorithm using O(log²n) steps with n processors on a EREW model.

Original language	English
Title of host publication	Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	26-31
Number of pages	6
ISBN (Electronic)	0818620870, 9780818620874
DOIs	https://doi.org/10.1109/SPDP.1990.143502
State	Published - 1990
Event	IEEE Symposium on Parallel and Distributed Processing - Dallas, United States Duration: Dec 9 1990 → Dec 13 1990 Conference number: 2 https://ieeexplore.ieee.org/servlet/opac?punumber=314

Publication series

Name	Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990

Conference

Conference	IEEE Symposium on Parallel and Distributed Processing
Abbreviated title	IEEE SPDP
Country/Territory	United States
City	Dallas
Period	12/9/90 → 12/13/90
Internet address	https://ieeexplore.ieee.org/servlet/opac?punumber=314

Scopus Subject Areas

Computer Networks and Communications
Hardware and Architecture

Access to Document

10.1109/SPDP.1990.143502

Cite this

Liang, Y., Dhall, S. K., & Lakshmivarahan, S. (1990). Parallel algorithms for ranking of trees. In Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990 (pp. 26-31). Article 143502 (Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SPDP.1990.143502

@inproceedings{c3f41912d82e451581e0537296ee6610,

title = "Parallel algorithms for ranking of trees",

abstract = "Ranking a tree is defined as a mapping rho of the nodes to the set (1, 2,...) such that if there is a path from u to v and rho (u)= rho (v) then there is a node w on the path from u to v such that rho (w)> rho (u). The highest number assigned to the node is called the rank number of the mapping. A mapping rho with the smallest rank number is called optimal ranking. The best known serial algorithm takes O(n) time for the optimal node ranking. However, the problem of finding the optimal tree ranking appears to be highly sequential. It remains open whether it is in NC. The paper proposes a fast parallel algorithm for finding approximate optimal node ranking of trees using O(logn) steps with n2 processors on a CRCW PRAM and an efficient parallel algorithm using O(log2n) steps with n processors on a EREW model.",

author = "Y. Liang and Dhall, {S. K.} and S. Lakshmivarahan",

note = "Publisher Copyright: {\textcopyright} 1990 IEEE.; IEEE Symposium on Parallel and Distributed Processing ; Conference date: 09-12-1990 Through 13-12-1990",

year = "1990",

doi = "10.1109/SPDP.1990.143502",

language = "English",

series = "Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "26--31",

booktitle = "Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990",

address = "United States",

url = "https://ieeexplore.ieee.org/servlet/opac?punumber=314",

}

Liang, Y, Dhall, SK & Lakshmivarahan, S 1990, Parallel algorithms for ranking of trees. in Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990., 143502, Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990, Institute of Electrical and Electronics Engineers Inc., pp. 26-31, IEEE Symposium on Parallel and Distributed Processing, Dallas, Texas, United States, 12/9/90. https://doi.org/10.1109/SPDP.1990.143502

Parallel algorithms for ranking of trees. / Liang, Y.; Dhall, S. K.; Lakshmivarahan, S.
Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990. Institute of Electrical and Electronics Engineers Inc., 1990. p. 26-31 143502 (Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990).

Research output: Contribution to book or proceeding › Conference article › peer-review

TY - GEN

T1 - Parallel algorithms for ranking of trees

AU - Liang, Y.

AU - Dhall, S. K.

AU - Lakshmivarahan, S.

N1 - Conference code: 2

PY - 1990

Y1 - 1990

N2 - Ranking a tree is defined as a mapping rho of the nodes to the set (1, 2,...) such that if there is a path from u to v and rho (u)= rho (v) then there is a node w on the path from u to v such that rho (w)> rho (u). The highest number assigned to the node is called the rank number of the mapping. A mapping rho with the smallest rank number is called optimal ranking. The best known serial algorithm takes O(n) time for the optimal node ranking. However, the problem of finding the optimal tree ranking appears to be highly sequential. It remains open whether it is in NC. The paper proposes a fast parallel algorithm for finding approximate optimal node ranking of trees using O(logn) steps with n2 processors on a CRCW PRAM and an efficient parallel algorithm using O(log2n) steps with n processors on a EREW model.

AB - Ranking a tree is defined as a mapping rho of the nodes to the set (1, 2,...) such that if there is a path from u to v and rho (u)= rho (v) then there is a node w on the path from u to v such that rho (w)> rho (u). The highest number assigned to the node is called the rank number of the mapping. A mapping rho with the smallest rank number is called optimal ranking. The best known serial algorithm takes O(n) time for the optimal node ranking. However, the problem of finding the optimal tree ranking appears to be highly sequential. It remains open whether it is in NC. The paper proposes a fast parallel algorithm for finding approximate optimal node ranking of trees using O(logn) steps with n2 processors on a CRCW PRAM and an efficient parallel algorithm using O(log2n) steps with n processors on a EREW model.

UR - http://www.scopus.com/inward/record.url?scp=0042514758&partnerID=8YFLogxK

U2 - 10.1109/SPDP.1990.143502

DO - 10.1109/SPDP.1990.143502

M3 - Conference article

AN - SCOPUS:0042514758

T3 - Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990

SP - 26

EP - 31

BT - Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - IEEE Symposium on Parallel and Distributed Processing

Y2 - 9 December 1990 through 13 December 1990

ER -

Liang Y, Dhall SK, Lakshmivarahan S. Parallel algorithms for ranking of trees. In Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990. Institute of Electrical and Electronics Engineers Inc. 1990. p. 26-31. 143502. (Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990). doi: 10.1109/SPDP.1990.143502

Parallel algorithms for ranking of trees

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this