The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages

de Ridder, Hendrik Nicolaas; de Ridder, Natalia

The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages

Dateien

DeRidder_279035.pdfGröße: 891.72 KBDownloads: 331

Datum

2014

Autor:innen

de Ridder, Hendrik Nicolaas

de Ridder, Natalia

Open Access-Veröffentlichung

Open Access Green

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Beitrag zu einem Konferenzband

Publikationsstatus

Published

Erschienen in

GIESE, Holger, ed., Barbara KÖNIG, ed.. Graph Transformation. Cham: Springer International Publishing, 2014, pp. 192-206. Lecture Notes in Computer Science. 8571. ISBN 978-3-319-09107-5. Available under: doi: 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

Schlagwörter

graph grammar, graph class, induced subgraph

Zitieren

ISO 690

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, 2014, pp. 192-206. Lecture Notes in Computer Science. 8571. ISBN 978-3-319-09107-5. Available under: doi: 10.1007/978-3-319-09108-2_13

BibTex

@inproceedings{deRidder2014Subgr-27903,
  year={2014},
  doi={10.1007/978-3-319-09108-2_13},
  title={The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages},
  number={8571},
  isbn={978-3-319-09107-5},
  publisher={Springer International Publishing},
  address={Cham},
  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: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/server/rdf/resource/123456789/27903">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>de Ridder, Natalia</dc:creator>
    <dc:creator>de Ridder, Hendrik Nicolaas</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2014-07-15T13:20:53Z</dcterms:available>
    <dc:contributor>de Ridder, Natalia</dc:contributor>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/27903/2/DeRidder_279035.pdf"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/27903"/>
    <dc:rights>terms-of-use</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>
    <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:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:title>The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages</dcterms:title>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/27903/2/DeRidder_279035.pdf"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2014-07-15T13:20:53Z</dc:date>
    <dc:language>eng</dc:language>
    <dcterms:issued>2014</dcterms:issued>
    <dc:contributor>de Ridder, Hendrik Nicolaas</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja