• Medientyp: Sonstige Veröffentlichung; Elektronischer Konferenzbericht
  • Titel: The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages
  • Beteiligte: de Ridder, Hendrik Nicolaas [Verfasser:in]; de Ridder, Natalia [Verfasser:in]
  • Erschienen: KOPS - The Institutional Repository of the University of Konstanz, 2014
  • Sprache: Englisch
  • DOI: https://doi.org/10.1007/978-3-319-09108-2_13
  • Schlagwörter: induced subgraph ; graph class ; graph grammar ; Graphentheorie
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: 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. ; published
  • Zugangsstatus: Freier Zugang
  • Rechte-/Nutzungshinweise: Urheberrechtsschutz