The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages


Dateien zu dieser Ressource

Prüfsumme: MD5:d88e278b9ee789bfb15a37d9b695d672

DE RIDDER, Hendrik Nicolaas, Natalia DE RIDDER, 2014. The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages. In: GIESE, Holger, ed., Barbara KÖNIG, ed.. Graph Transformation. Cham:Springer International Publishing, pp. 192-206. ISBN 978-3-319-09107-5

@inproceedings{de Ridder2014Subgr-27903, title={The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages}, year={2014}, doi={10.1007/978-3-319-09108-2_13}, number={8571}, isbn={978-3-319-09107-5}, address={Cham}, publisher={Springer International Publishing}, series={Lecture Notes in Computer Science}, booktitle={Graph Transformation}, pages={192--206}, editor={Giese, Holger and König, Barbara}, author={de Ridder, Hendrik Nicolaas and de Ridder, Natalia} }

<rdf:RDF xmlns:rdf="" xmlns:bibo="" xmlns:dc="" xmlns:dcterms="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dc:contributor>de Ridder, Natalia</dc:contributor> <dc:date rdf:datatype="">2014-07-15T13:20:53Z</dc:date> <dc:rights>deposit-license</dc:rights> <dcterms:bibliographicCitation>Graph Transformation : 7th International Conference, ICGT 2014, Held as Part of STAF 2014, York, UK, July 22-24, 2014, Proceedings / Holger Giese ... (eds.). - Cham : Springer, 2014. - S. 192-206. - (Lecture Notes in Computer Science ; 8571). - ISBN 978-3-319-09107-5</dcterms:bibliographicCitation> <dc:language>eng</dc:language> <bibo:uri rdf:resource=""/> <dcterms:available rdf:datatype="">2014-07-15T13:20:53Z</dcterms:available> <dc:contributor>de Ridder, Hendrik Nicolaas</dc:contributor> <dcterms:title>The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages</dcterms:title> <dc:creator>de Ridder, Hendrik Nicolaas</dc:creator> <dcterms:rights rdf:resource=""/> <dcterms:abstract xml:lang="eng">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.</dcterms:abstract> <dcterms:issued>2014</dcterms:issued> <dc:creator>de Ridder, Natalia</dc:creator> </rdf:Description> </rdf:RDF>

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

DeRidder_279035.pdf 63

Das Dokument erscheint in:

KOPS Suche


Mein Benutzerkonto