
A graph class is called A-free if every graph in the class has no graph in the set A as an induced subgraph. Such characterisations by forbidden induced subgraphs are (among other purposes) very useful for determining whether A-free is a subclass of B-free, by determining whether every graph in B has some graph in A as an induced subgraph. This requires solving the Subgraph Isomorphism Problem, which is NP-complete in general, but for which effective practical algorithms for general and specific purposes exist. However, if B is infinite, these algorithms cannot be used. We introduce Head-Mid-Tail grammars (a special case of hyperedge replacement grammars) which have the property that if an infinite set B can be defined by a Head-Mid-Tail grammar then it is decidable whether every graph in B contains some graph from a finite set A of graphs as an induced subgraph, thereby solving the A-free ⊆ B-free problem. Moreover, our algorithm is both simple and efficient enough to be practical.
info:eu-repo/classification/gnd/Graphentheorie, graph class, induced subgraph, graph grammar, info:eu-repo/classification/ddc/004
info:eu-repo/classification/gnd/Graphentheorie, graph class, induced subgraph, graph grammar, info:eu-repo/classification/ddc/004
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
