TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Engineering motif search for large graphs

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Otsikko2015 Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX)
Sivut104-118
Sivumäärä15
ISBN (elektroninen)978-1-61197-375-4
DOI - pysyväislinkit
TilaJulkaistu - 2015
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaWORKSHOP ON ALGORITHM ENGINEERING AND EXPERIMENTS -
Kesto: 1 tammikuuta 1900 → …

Julkaisusarja

NimiWorkshop on Algorithm Engineering and Experiments
ISSN (painettu)2164-0300

Conference

ConferenceWORKSHOP ON ALGORITHM ENGINEERING AND EXPERIMENTS
LyhennettäALENEX
Ajanjakso1/01/00 → …

Tiivistelmä

In the graph motif problem, we are given as input a vertexcolored graph H (the host graph) and a multiset of colors M (the motif). Our task is to decide whether H has a connected set of vertices whose multiset of colors agrees with M. The graph motif problem is NP-complete but known to admit parameterized algorithms that run in linear time in the size of H. We demonstrate that algorithms based on constrained multilinear sieving are viable in practice, scaling to graphs with hundreds of millions of edges as long as M remains small. Furthermore, our implementation is topologyinvariant relative to the host graph H, meaning only the most crude graph parameters (number of edges and number of vertices) suffice in practice to determine the algorithm performance.

!!ASJC Scopus subject areas

Julkaisufoorumi-taso

Tilastokeskuksen tieteenalat