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}, }

Powered by bibtexbrowser