Publikation:

The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages

Vorschaubild

Dateien

DeRidder_279035.pdf
DeRidder_279035.pdfGröße: 891.72 KBDownloads: 364

Datum

2014

Autor:innen

de Ridder, Natalia

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
http://nbn-resolving.de/urn:nbn:de:bsz:352-279035
DOI (zitierfähiger Link)
https://doi.org/10.1007/978-3-319-09108-2_13
ArXiv-ID

Internationale Patentnummer

Link zur Lizenz
Urheberrechtlich geschützt

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

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.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

graph grammar, graph class, induced subgraph

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690DE 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>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen