Efficient Parallel Algorithms For Some Tree Layout Problems

    Authors

    J. Diaz; A. Gibbons; G. Pantziou; M. Serna; P. Spirakis;J. Toran

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Keywords

    Computer Science, Theory & Methods

    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.

    Journal Title

    Computing and Combinatorics

    Volume

    959

    Publication Date

    1-1-1995

    Document Type

    Article

    Language

    English

    First Page

    313

    Last Page

    323

    WOS Identifier

    WOS:A1995BE73M00033

    ISSN

    0302-9743; 3-540-60216-X

    Share

    COinS