• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Examples on Parallel Complexity of Signed Graphs

Tero Harju, Chang Li, Ion Petre, Examples on Parallel Complexity of Signed Graphs. TUCS Technical Reports 811, Turku Centre for Computer Science, 2007.

Abstract:

We consider a graph-based model for the study of
parallelism in ciliate gene assembly,%%, see~\cite{EHPPR:book},
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.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaLiPe07a,
  title = {Examples on Parallel Complexity of Signed Graphs},
  author = {Harju, Tero and Li, Chang and Petre, Ion},
  number = {811},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2007},
  ISBN = {978-952-12-1889-7},
}

Belongs to TUCS Research Unit(s): Computational Biomodeling Laboratory (Combio Lab)

Edit publication