Title

Efficient Parallel Algorithms For Some Tree Layout Problems

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 ArC’ for trees, and the second problem also is in ArC for bounded degree trees.

Publication Date

1-1-1995

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

959

Number of Pages

313-323

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/BFb0030846

Socpus ID

84957595101 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84957595101

This document is currently not available here.

Share

COinS