The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages

Zitieren

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="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/27903"> <dc:contributor>de Ridder, Natalia</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">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="http://kops.uni-konstanz.de/handle/123456789/27903"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">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="http://nbn-resolving.org/urn:nbn:de:bsz:352-20140905103605204-4002607-1"/> <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


Stöbern

Mein Benutzerkonto