Massimo Equi

All Publications

Google Scholar

DBLP

Selected Publications

Lower bounds for SMLG (String Matching in Labelled Graphs)

• Massimo Equi, Veli Mäkinen, Alexandru I. Tomescu, Roberto Grossi
  On the Complexity of String Matching for Graphs
  ACM Transactions on Algorithms (TALG), 2023
  DOI: 10.4230/LIPIcs.ICALP.2019.55
  Extended version of a paper in ICALP 2019

• Massimo Equi, Veli Mäkinen, Alexandru I. Tomescu
  Graphs Cannot Be Indexed in Polynomial Time for Sub-quadratic Time String Matching, Unless SETH Fails
  Theoretical Computer Science, 2023
  DOI: 10.1016/j.tcs.2023.114128
  Extended version of a paper in SOFSEM 2021
  Preprint: arxiv.org/abs/2002.00629

Quantum algorithm for SMLG

• Massimo Equi, Arianne Meijer-van de Griend, Veli Mäkinen
  From Bit-Parallelism to Quantum String Matching for Labelled Graphs
  CPM 2023
  DOI: 10.4230/LIPIcs.CPM.2023.9

Founder graphs

• Massimo Equi, Tuukka Norri, Jarno Alanko, Bastien Cazaux, Alexandru I. Tomescu, Veli Mäkinen
  Algorithms and Complexity on Indexing Founder Graphs
  Algorithmica, 2023
  DOI: 10.1007/s00453-022-01007-w
  Extended version of a paper in WABI 2020 and a paper in ISAAC 2021