Indexes for Jumbled Pattern Matching in Strings, Trees, and Graphs

Cicalese, Ferdinando; Travis, Gagie; Emanuele, Giaquinta; Eduardo Sany Laber,; Liptak, Zsuzsanna; Rizzi, Romeo; Tomescu, Alexandru I.

doi:10.1007/978-3-319-02432-5_10

CATALOGO DEI PRODOTTI DELLA RICERCA

IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.

We consider how to index strings, trees and graphs for jum- bled pattern matching when we are asked to return a match if one exists. For example, we show how, given a tree containing two colours, we can build a quadratic-space index with which we can find a match in time proportional to the size of the match. We also show how we need only linear space if we are content with approximate matches.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/614553

Titolo:	Indexes for Jumbled Pattern Matching in Strings, Trees, and Graphs
Autori:	Cicalese, Ferdinando Travis Gagie Emanuele Giaquinta Eduardo Sany Laber Liptak, Zsuzsanna RIZZI, ROMEO Alexandru I. Tomescu mostra contributor esterni nascondi contributor esterni
Data di pubblicazione:	2013
Serie:	LECTURE NOTES IN COMPUTER SCIENCE
Abstract:	We consider how to index strings, trees and graphs for jum- bled pattern matching when we are asked to return a match if one exists. For example, we show how, given a tree containing two colours, we can build a quadratic-space index with which we can find a match in time proportional to the size of the match. We also show how we need only linear space if we are content with approximate matches.
Handle:	http://hdl.handle.net/11562/614553
ISBN:	9783319024318
Appare nelle tipologie:	04.01 Contributo in atti di convegno

File in questo prodotto:

Non ci sono file associati a questo prodotto.

Citazioni

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.