Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Pattern Discovery and Listing in Graphs
verfasst von : Roberto Grossi
Erschienen in: String Processing and Information Retrieval
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Graphs are gaining increasing popularity in many application domains as they have the potential of modeling binary relations among entities. Along with textual and multimedia data, they are the main sources for producing large data sets. It is natural to ask how it is easy to extend the notion of patterns typically found in string matching and sequence analysis, to graphs and real-life networks. Unfortunately, even the basic problem of finding a simple path in a graph is NP-hard since this can establish if the graph is Hamiltonian. Also, the number of patterns can be exponentially large in the size of the graph, thus listing them is a challenge. We will discuss some output-sensitive and parameterized algorithms for listings patterns that are paths, cycles and trees, and provide a notion of “certificate” to attain this goal. This is joint work with Rui Ferreira.