Navigation/Menü: Links auf weitere Seiten dieser Website
Objekt-Metadaten
| Bypass strong V-structures and find an isomorphic labelled subgraph in linear time Dörr, Heiko |
| Haupttitel | Bypass strong V-structures and find an isomorphic labelled subgraph in linear time |
| Autor | Dörr, Heiko |
| Seitenzahl | 12 S. |
| Schriftenreihe | Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 94,8 |
| Fachbereich/Einrichtung | FB Mathematik und Informatik |
| Arbeitsbereich/Institut | Institut für Informatik |
| Erscheinungsjahr | 1994 |
| Dokumente | pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
|
| DDC | 004 Datenverarbeitung; Informatik |
| Dokumententyp/-Sammlungen | Report |
| Medientyp/Format | Text |
| Abstract | This paper identifies a condition for which the existence of an isomorphic subgraph can be decided in linear time. The condition is evaluated in two steps. First the host graph is analysed to determine its strong V-structures. Then the guest graph must be appropriately represented. If this representation exists, the given algorithm constructively decides the subgraph isomorphism problem for the guest and the host graph in linear time. The results applies especially to the implementation of graph rewriting systems. An isomorphic subgraph must be determined automatically in each rewriting step. Thus the efficient solution presented in this paper is an important progress for any implementation project. |
| Sprache | Englisch |
| Rechte | Nutzungsbedingungen |
| Zugriffstatistik | |
| Statische URL | http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001863 |
| Erstellt am | 12.05.2009 - 15:26:16 |
| Letzte Änderung | 04.04.2013 - 09:33:24 |
