Loose Graph Simulations

Alessio Mansutti, Marino Miculan, Marco Peressotti

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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 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
Title of host publicationSoftware Technologies: Applications and Foundations : STAF 2017 Collocated Workshops, Marburg, Germany, July 17-21, 2017, Revised Selected Papers
EditorsMartina Seidl, Steffen Zschaler
PublisherSpringer
Publication date2018
Pages109-126
ISBN (Print)978-3-319-74729-3
ISBN (Electronic)978-3-319-74730-9
DOIs
Publication statusPublished - 2018
EventSoftware Technologies: Applications and Foundations Conference - Marburg, Germany
Duration: 17. Jul 201721. Jul 2017

Conference

ConferenceSoftware Technologies: Applications and Foundations Conference
Country/TerritoryGermany
CityMarburg
Period17/07/201721/07/2017
SeriesLecture Notes in Computer Science
Volume10748
ISSN0302-9743
SeriesProgramming and Software Engineering
Volume10748

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.

Cite this