An efficient parallel algorithm for building the separating tree期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

An efficient parallel algorithm for building the separating tree

Authors:	Yijie Han Sanjeev Saxena Xiaojun Shen

Affiliation:	1. School of Computing and Engineering, University of Missouri at Kansas City, 5100 Rockhill Road, Kansas City, MO 64110, USA;2. Computer Science and Engineering, Indian Institute of Technology, Kanpur-208 016, India

Abstract:	We present an efficient parallel algorithm for building the separating tree for a separable permutation. Our algorithm runs in O(log²n) $O ({log}^{2} n)$ time using O(nlog^1.5n) $O (n {log}^{1.5} n)$ operations on the CREW PRAM and O(log²n) $O ({log}^{2} n)$ time using O(nlognloglogn) $O (n log n log log n)$ operations on the COMMON CRCW PRAM.

Keywords:	Algorithms Parallel algorithms Separable permutation
本文献已被 ScienceDirect 等数据库收录！