UNSPECIFIED (1997) Parallel algorithms for the minimum cut and the minimum length tree layout problems. In: 1st Annual Conference on Computing and Combinatorics (COCOON 95), AUG 24-26, 1995, XIAN, PEOPLES R CHINA.

Full text not available from this repository.

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 is in NC for bounded degree trees. To the best of our knowledge, these are the first parallel algorithms for the minimum length and the minimum cut linear arrangement problems.

Item Type:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Journal or Publication Title:	THEORETICAL COMPUTER SCIENCE
Publisher:	ELSEVIER SCIENCE BV
ISSN:	0304-3975
Date:	30 July 1997
Volume:	181
Number:	2
Number of Pages:	21
Page Range:	pp. 267-287
Publication Status:	Published
Title of Event:	1st Annual Conference on Computing and Combinatorics (COCOON 95)
Location of Event:	XIAN, PEOPLES R CHINA
Date(s) of Event:	AUG 24-26, 1995
URI:	http://wrap.warwick.ac.uk/id/eprint/16538

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item