Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Online Algorithm
Parallel Algorithm
Subscribe
Academic
Publications
An OnLine Parallel Algorithm for Node Ranking of Trees
An OnLine Parallel Algorithm for Node Ranking of Trees,10.1007/9783642030956_37,Chiawei Lee,Justie Sutzu Juan,Tailung Wu
Edit
An OnLine Parallel Algorithm for Node Ranking of Trees
BibTex

RIS

RefWorks
Download
Chiawei Lee
,
Justie Sutzu Juan
,
Tailung Wu
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 online 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 online 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.
Conference:
International Conference on Algorithms and Architectures for Parallel Processing  ICA3PP
, pp. 384395, 2009
DOI:
10.1007/9783642030956_37
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
References
(20)
Biconvex graphs: ordering and algorithms
(
Citations: 8
)
Nesrine Abbas
,
Lorna K. Stewart
Journal:
Discrete Applied Mathematics  DAM
, vol. 103, no. 13, pp. 119, 2000
Parallel computation: models and methods
(
Citations: 265
)
S. G. Akl
Published in 1997.
Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height
(
Citations: 45
)
Hans L. Bodlaender
,
John R. Gilbert
,
Ton Kloks
,
Hjálmtyr Hafsteinsson
Conference:
Workshop on GraphTheoretic Concepts in Computer Science  WG
, pp. 112, 1991
The multifrontal solution of inde nite sparse symmetric linear equations
(
Citations: 173
)
I. S. Du
,
J. K. Reid
Journal:
ACM Transactions on Mathematical Software  TOMS
, 1983
On vertex ranking of a starlike graph
(
Citations: 11
)
Sunyuan Hsieh
Journal:
Information Processing Letters  IPL
, vol. 82, no. 3, pp. 131135, 2002