Loose Graph Simulations

Alessio Mansutti, Marino Miculan, Marco Peressotti

Research output: Working paper › Research

Abstract

We introduce loose graph simulations (LGS), a new notion about labelled graphs which subsumes in an intuitive and natural way subgraph isomorphism (SGI), regular language pattern matching (RLPM) and graph simulation (GS). Being a unification of all these notions, LGS allows us to express directly also problems which are "mixed" instances of previous ones, and hence which would not fit easily in any of them. After the definition and some examples, we show that the problem of finding loose graph simulations is NP-complete, we provide a formal translation of SGI, RLPM, and GS into LGSs, and we give the representation of a problem which extends both SGI and RLPM. Finally, we identify a subclass of the LGS problem that is polynomial.
Original languageEnglish
Publication statusPublished - 23. May 2017

Keywords

  • Graph theory
  • Graph transformation
  • Complexity
  • Graph Isomorphism
  • Formal graph languages

Fingerprint

Dive into the research topics of 'Loose Graph Simulations'. Together they form a unique fingerprint.
View full fingerprint
  • 1 Article in proceedings

  • Loose Graph Simulations

    Mansutti, A., Miculan, M. & Peressotti, M., 2018, Software Technologies: Applications and Foundations: STAF 2017 Collocated Workshops, Marburg, Germany, July 17-21, 2017, Revised Selected Papers. Seidl, M. & Zschaler, S. (eds.). Springer, p. 109-126 (Lecture Notes in Computer Science, Vol. 10748). (Programming and Software Engineering, Vol. 10748).

    Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Cite this