commit d40187228225de450c82d92d4c59a822de1d491f
parent d9218bfddbee7a71253e066f12f479aac749569a
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 25 Apr 2025 14:00:05 +0200
commit with codex
Diffstat:
4 files changed, 15 insertions(+), 2 deletions(-)
diff --git a/enumeration_strings b/enumeration_strings
@@ -10,6 +10,7 @@
- [enumeration_streaming]
- [enumeration_parallel]
- [enumeration_spanner]
+- [enumeration_maximal_common_subsequence]
Generalizations:
diff --git a/maximal_common_subsequence b/maximal_common_subsequence
@@ -5,8 +5,7 @@
- [longest_common_subsequence] is MCS but not necessarily vice-versa
- [PTIME] to compute MCS for an unbounded number of multiple input strings: [hirota2023fast]
-[enumeration] in [conte2019polynomial]
-- but there is also a hardness result, Maximal Common Subsequence Enumeration is Hard #todo
+[enumeration_maximal_common_subsequence]
- warning! you can compute greedily a common sequence between 2 strings by extending it to the right
- but it is not necessarily an MCS, it may still be possible to extend it by an insertion
diff --git a/simple_path b/simple_path
@@ -2,6 +2,8 @@
A [path] with no repeated [vertices]
+[simple_path_problem]
+
Up: [path]
See also: [trail], [walk]
diff --git a/simple_path_rpq_problem b/simple_path_rpq_problem
@@ -0,0 +1,11 @@
+# Simple path rpq problem
+
+Decide if there is a [simple_path] satisfing a [RPQ]
+
+Topic of the [simple_path_trichotomy]
+
+Also [enumeration]: [simple_path_rpq_enumeration]
+
+Up: [simple_path_problem], [RPQ]
+
+See also: [simple_path_modulo]
