---
res:
bibo_abstract:
- We consider the problem of transforming a given graph G_s into a desired graph
G_t by applying a minimum number of primitives from a particular set of local
graph transformation primitives. These primitives are local in the sense that
each node can apply them based on local knowledge and by affecting only its 1-neighborhood.
Although the specific set of primitives we consider makes it possible to transform
any (weakly) connected graph into any other (weakly) connected graph consisting
of the same nodes, they cannot disconnect the graph or introduce new nodes into
the graph, making them ideal in the context of supervised overlay network transformations.
We prove that computing a minimum sequence of primitive applications (even centralized)
for arbitrary G_s and G_t is NP-hard, which we conjecture to hold for any set
of local graph transformation primitives satisfying the aforementioned properties.
On the other hand, we show that this problem admits a polynomial time algorithm
with a constant approximation ratio.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Christian
foaf_name: Scheideler, Christian
foaf_surname: Scheideler
foaf_workInfoHomepage: http://www.librecat.org/personId=20792
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Setzer, Alexander
foaf_surname: Setzer
foaf_workInfoHomepage: http://www.librecat.org/personId=11108
bibo_doi: 10.4230/LIPICS.ICALP.2019.150
bibo_volume: 132
dct_date: 2019^xs_gYear
dct_language: eng
dct_publisher: Dagstuhl Publishing@
dct_subject:
- Graphs transformations
- NP-hardness
- approximation algorithms
dct_title: On the Complexity of Local Graph Transformations@
...