Graphs Cannot Be Indexed in Polynomial Time for Sub-quadratic Time String Matching, Unless SETH Fails.

Massimo Equi, Veli Mkinen, Alexandru I. Tomescu

Browse the full SOFSEM paper archive.