Publikationstyp: | Beitrag zu einer Konferenz |
URI (zitierfähiger Link): | http://nbn-resolving.de/urn:nbn:de:bsz:352-279035 |
Autor/innen: | de Ridder, Hendrik Nicolaas; de Ridder, Natalia |
Erscheinungsjahr: | 2014 |
Erschienen in: | Graph Transformation / Giese, Holger; König, Barbara (Hrsg.). - Cham : Springer International Publishing, 2014. - (Lecture Notes in Computer Science ; 8571). - S. 192-206. - ISBN 978-3-319-09107-5 |
DOI (zitierfähiger Link): | https://dx.doi.org/10.1007/978-3-319-09108-2_13 |
Zusammenfassung: |
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.
|
Fachgebiet (DDC): | 004 Informatik |
Normierte Schlagwörter (GND): | Graphentheorie |
Schlagwörter: | graph grammar, graph class, induced subgraph |
Link zur Lizenz: | Nutzungsbedingungen |
Universitätsbibliographie: | Ja |
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. Available under: doi: 10.1007/978-3-319-09108-2_13
@inproceedings{deRidder2014Subgr-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:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" 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> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/27903/2/DeRidder_279035.pdf"/> <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> <dcterms:rights rdf:resource="https://kops.uni-konstanz.de/page/termsofuse"/> <dc:language>eng</dc:language> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <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> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:title>The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages</dcterms:title> <dc:creator>de Ridder, Hendrik Nicolaas</dc:creator> <dc:rights>terms-of-use</dc:rights> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/27903/2/DeRidder_279035.pdf"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <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>
DeRidder_279035.pdf | 69 |