The Library
Efficient parallel algorithms for some tree layout problems
Tools
UNSPECIFIED (1995) Efficient parallel algorithms for some tree layout problems. In: 1st Annual International Computing and Combinatorics Conference (COCOON 95), XIAN, PEOPLES R CHINA, AUG 24-26, 1995. Published in: COMPUTING AND COMBINATORICS, 959 pp. 313-323. ISBN 3-540-60216-X. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
The minimum cut and minimum length linear arrangement problems usually occur in solving wiring problems and have a lot in common with job sequencing questions. Both problems are NP-complete for general graphs and in P for trees. We present here two parallel algorithms for the CREW PRAM. The first solves the minimum length linear arrangement problem for trees and the second solves the minimum cut arrangement for trees. We prove that the first problem belongs to NC for trees, and the second problem also is in NC for bounded degree trees.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
Journal or Publication Title: | COMPUTING AND COMBINATORICS | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-60216-X | ||||
ISSN: | 0302-9743 | ||||
Editor: | Du, DZ and Li, M | ||||
Official Date: | 1995 | ||||
Dates: |
|
||||
Volume: | 959 | ||||
Number of Pages: | 11 | ||||
Page Range: | pp. 313-323 | ||||
Publication Status: | Published | ||||
Title of Event: | 1st Annual International Computing and Combinatorics Conference (COCOON 95) | ||||
Location of Event: | XIAN, PEOPLES R CHINA | ||||
Date(s) of Event: | AUG 24-26, 1995 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |