On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree

Massimo Equi (1) , Roberto Grossi (2, 3) , Veli Makinen (1)

1 Helsingin yliopisto = Helsingfors universitet = University of Helsinki
2 DI - Dipartimento di Informatica [Pisa]
3 ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale

Mots clés: labeled graphs; string matching; string search; strong exponential time hypothesis; variation graphs; 2012 ACM Subject Classification Mathematics of computing → Graph algorithms Theory of computation → Problems; exact pattern matching; graph query; graph search; heterogeneous networks

Domaines: Informatique [cs]

Massimo Equi, Roberto Grossi, Veli Makinen. On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree. ICALP 2019 - 46th International Colloquium on Automata, Languages and Programming, Jul 2019, Patras, Greece. pp.1-15. ⟨hal-02338498⟩