Graph Multiset Transformation as a Framework for Massively Parallel Computation

被引：0
|
作者：
Kreowski, Hans-Joerg [1 ]
Kuske, Sabine [1 ]
机构：
[1] Univ Bremen, Dept Comp Sci, D-28334 Bremen, Germany
来源：
GRAPH TRANSFORMATIONS, ICGT 2008 | 2008年 / 5214卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, graph multiset transformation is introduced and studied as a novel type of parallel graph transformation. The basic idea is that graph transformation rules may be applied to all or at least some members of a multiset of graphs simultaneously providing a computational step with the possibility Of massive parallelism in this way. As a consequence, graph problems in the class NP can be solved by a single computation of polynomial length for each input graph.
引用
收藏
页码：351 / 365
页数：15
相关论文
共 50 条
  • [1] Graph multiset transformation: a new framework for massively parallel computation inspired by DNA computing
    Kreowski, Hans-Joerg
    Kuske, Sabine
    NATURAL COMPUTING, 2011, 10 (02) : 961 - 986
  • [2] Graph multiset transformation: a new framework for massively parallel computation inspired by DNA computing
    Hans-Jörg Kreowski
    Sabine Kuske
    Natural Computing, 2011, 10 : 961 - 986
  • [3] Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
    Czumaj, Artur
    Davies, Peter
    Parter, Merav
    PROCEEDINGS OF THE 32ND ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA '20), 2020, : 175 - 185
  • [4] Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
    Czumaj, Artur
    Davies, Peter
    Parter, Merav
    ACM TRANSACTIONS ON ALGORITHMS, 2021, 17 (02)
  • [5] Parallel Training via Computation Graph Transformation
    Wang, Fei
    Chen, Guoyang
    Zhang, Weifeng
    Rompf, Tiark
    2019 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA), 2019, : 3430 - 3439
  • [6] Explainable graph clustering via expanders in the massively parallel computation model
    Aghamolaei, Sepideh
    Ghodsi, Mohammad
    INFORMATION SCIENCES, 2024, 677
  • [7] GRAPH GRAMMAR BASED SPECIFICATION OF INTERCONNECTION STRUCTURES FOR MASSIVELY PARALLEL COMPUTATION
    BAILEY, DA
    CUNY, JE
    LECTURE NOTES IN COMPUTER SCIENCE, 1987, 291 : 73 - 85
  • [8] On the Hardness of Massively Parallel Computation
    Chung, Kai-Min
    Ho, Kuan-Yi
    Sun, Xiaorui
    PROCEEDINGS OF THE 32ND ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA '20), 2020, : 153 - 162
  • [9] Parallel Machines for Multiset Transformation and their Programming Style
    Banätre, J.-P.
    Coutant, A.
    Métayer, D. Le
    IT - Information Technology, 1988, 30 (02): : 99 - 109
  • [10] Massively parallel computation on anisotropic meshes
    Digonnet, H.
    Silva, L.
    Coupez, T.
    Adaptive Modeling and Simulation 2013 - Proceedings of the 6th International Conference on Adaptive Modeling and Simulation, ADMOS 2013, 2013, : 199 - 211
12345