Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Engineering Motif Search for Large Graphs

In English

Författare

  • Andreas Björklund
  • Petteri Kaski
  • Lukasz Kowalik
  • Juho Lauri

Redaktör

  • Ulrik Brandes
  • David Eppstein

Summary, in English

In the graph motif problem, we are given as input a vertex-colored 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 topology-invariant 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.

Publiceringsår

2015

Språk

Engelska

Sidor

104-118

Publikation/Tidskrift/Serie

[Host publication title missing]

Dokumenttyp

Konferensbidrag

Ämne

  • Computer Science

Conference name

ALENEX

Conference date

2015-01-05

Status

Published

Projekt

  • Exact algorithms