Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.15
URN: urn:nbn:de:0030-drops-153068
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15306/
Archibald, Blair ; Burns, Kyle ; McCreesh, Ciaran ; Sevegnani, Michele
Practical Bigraphs via Subgraph Isomorphism
| pdf-format: |
|
Abstract
Bigraphs simultaneously model the spatial and non-spatial relationships between entities, and have been used for systems modelling in areas including biology, networking, and sensors. Temporal evolution can be modelled through a rewriting system, driven by a matching algorithm that identifies instances of bigraphs to be rewritten. The previous state-of-the-art matching algorithm for bigraphs with sharing is based on Boolean satisfiability (SAT), and suffers from a large encoding that limits scalability and makes it hard to support extensions. This work instead adapts a subgraph isomorphism solver that is based upon constraint programming to solve the bigraph matching problem. This approach continues to support bigraphs with sharing, is more open to other extensions and side constraints, and improves performance by over two orders of magnitude on a range of problem instances drawn from real-world mixed-reality, protocol, and conference models.
BibTeX - Entry
@InProceedings{archibald_et_al:LIPIcs.CP.2021.15,
author = {Archibald, Blair and Burns, Kyle and McCreesh, Ciaran and Sevegnani, Michele},
title = {{Practical Bigraphs via Subgraph Isomorphism}},
booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
pages = {15:1--15:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-211-2},
ISSN = {1868-8969},
year = {2021},
volume = {210},
editor = {Michel, Laurent D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15306},
URN = {urn:nbn:de:0030-drops-153068},
doi = {10.4230/LIPIcs.CP.2021.15},
annote = {Keywords: bigraphs, subgraph isomorphism, constraint programming, rewriting systems}
}
| Keywords: | bigraphs, subgraph isomorphism, constraint programming, rewriting systems | |
| Seminar: | 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 15.10.2021 | |
| Supplementary Material: | Software (Source Code): https://doi.org/10.5281/zenodo.5161185 |
