Academic
Publications
An On-Line Parallel Algorithm for Node Ranking of Trees

An On-Line Parallel Algorithm for Node Ranking of Trees,10.1007/978-3-642-03095-6_37,Chia-wei Lee,Justie Su-tzu Juan,Tai-lung Wu

An On-Line Parallel Algorithm for Node Ranking of Trees  
BibTex | RIS | RefWorks Download
A node ranking of a graph G = (V, E) is a proper node coloring C: V →ℕ such that any path in G with end nodes x, y fulfilling C(x) = C(y) contains an internal node z with C(z) > C(x). In the on-line version of the node ranking problem, the nodes v 1, v 2,..., v n are coming one by one in an arbitrary order; and only the edges of the induced subgraph G[{v 1, v 2,..., v i }] are known when the color for the node v i be chosen. And the assigned color can not be changed later. In this paper, we present a parallel algorithm to find an on-line node ranking for general tree. Our parallel algorithm needs O(nlog2 n ) time with using O(n 3 / log2 n) processors on CREW PRAM model.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.