Examples on Parallel Complexity of Signed Graphs (bibtex)
by Harju, Tero, Li, Chang and Petre, Ion
Abstract:
We consider a graph-based model for the study of parallelism in ciliate gene assembly, where a signed graph is associated to each micronuclear gene and the gene assembly is modeled as a graph rewriting process. We show that the complexity measure counting the number of steps needed to fully reduce a graph in parallel varies greatly. The general problem of whether there exists a finite upper bound for the graph parallel complexity remains open.
Reference:
Examples on Parallel Complexity of Signed Graphs (Harju, Tero, Li, Chang and Petre, Ion), Technical report 811, , 2007.
Bibtex Entry:
@TechReport{t144,
author   = {Harju, Tero AND Li, Chang AND Petre, Ion},
title    = {Examples on Parallel Complexity of Signed Graphs},
year     = {2007},
number   = {811},
abstract = {We consider a graph-based model for the study of parallelism in ciliate gene assembly, where a signed graph is associated to each micronuclear gene and the gene assembly is modeled as a graph rewriting process. We show that the complexity measure counting the number of steps needed to fully reduce a graph in parallel varies greatly. The general problem of whether there exists a finite upper bound for the graph parallel complexity remains open.},
file     = {HLP2007a.pdf:pdfs/HLP2007a.pdf:PDF},
}