The Complexity of Maximal Common Subsequence Enumeration
Summary: Enumerating maximal common subsequences across multiple strings is not output-polynomial unless P=NP, extending LCS hardness to maximal frequent subsequence mining. The work then analyzes parameterized complexity w.r.t. alphabet size, number of strings, and string length, yielding tractability insights for practical algorithms. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Giovanni Buzzega
- 2. Alessio Conte
- 3. Yasuaki Kobayashi
- 4. Kazuhiro Kurita
- 5. Giulia Punzi
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 13 | Mining Association Rules between Sets of Items in Large Databases | 1993 | SIGMOD | 0.0010864752 |
| 3,387 | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration | 2020 | PODS | 7.1573735e-05 |
| 5,043 | The Complexity of Mining Maximal Frequent Subgraphs | 2013 | PODS | 5.7411631e-05 |
Previous
Page 1 / 1
Next