The parallel complexity of signed graphs: Decidability results and an improved algorithm

DOI10.1016/j.tcs.2009.02.028zbMath1167.68022MaRDI QIDQ1019708

Ion Petre, Artiom Alhazov, Vladimir Rogozhin

Publication date: 4 June 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.02.028

zbMATH Keywords

algorithm; decidability; parallel complexity; signed graphs; ciliates; parallel gene assembly

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W10: Parallel algorithms in computer science

92C37: Cell biology

05C85: Graph algorithms (graph-theoretic aspects)

92D10: Genetics and epigenetics

05C22: Signed and weighted graphs