commit bc527cd8d4f21fd9346827e04a4825df5bade9c3
parent c19dafd9eeb3522bcf73ef63feb5d53e76a78186
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 17 Aug 2026 16:56:12 +0200
commit with codex
Diffstat:
13 files changed, 62 insertions(+), 7 deletions(-)
diff --git a/edge_hamiltonian_cycle b/edge_hamiltonian_cycle
@@ -0,0 +1,13 @@
+# Line graph hamiltonian cycle
+
+The [line_graph] of an [undirected_graph] has a [Hamiltonian_cycle] whenever the original graph has a [Hamiltonian_cycle]:
+- cf [balakrishnan2012textbook], Corollary 6.5.5
+- cf [harary1965eulerian]
+
+[Computational_problem]: [edge_hamiltonian_cycle_problem]
+
+Up: [line_graph], [hamiltonian_cycle]
+
+Aliases: edge hamiltonian cycle
+
+See also: [edge_hamiltonian_path]
diff --git a/edge_hamiltonian_path b/edge_hamiltonian_path
@@ -0,0 +1,11 @@
+# Edge hamiltonian path
+
+An *edge hamiltonian path* of an [undirected_graph] G is a [hamiltonian_path] of the [line_graph] of G
+
+For the corresponding [computational_problem], see the [edge_hamiltonian_path_problem]; it is [NP_complete] by [lai1993edge] already on [bipartite_graphs]
+
+Up: [hamiltonian_path], [line_graph]
+
+See also: [edge_hamiltonian_cycle]
+
+Aliases: line graph hamiltonian path
diff --git a/edge_hamiltonian_path_problem b/edge_hamiltonian_path_problem
@@ -0,0 +1,9 @@
+# Edge hamiltonian path problem
+
+The [computational_problem] of [deciding], given an [undirected_graph], whether it admits a [line_graph_hamiltonian_path], i.e., whether its [line_graph] has a [hamiltonian_path]
+
+It is [NP_complete] by [lai1993edge] already on [bipartite_graphs]
+
+Up: [decision_problem], [line_graph_hamiltonian_path]
+
+See also: [edge_hamiltonian_cycle_problem], [hamiltonian_path_problem]
diff --git a/hamiltonian_cycle b/hamiltonian_cycle
@@ -5,3 +5,5 @@
Up: [cycle]
See also: [graph_eulerian], [hamiltonian_path]
+
+Aliases: hamiltonian cycles
diff --git a/hamiltonian_cycle_problem b/hamiltonian_cycle_problem
@@ -3,6 +3,7 @@
The [decision_problem] of whether an input [undirected_graph] admits a [Hamiltonian_cycle], or the [function_problem] of finding one
It is [NP_hard], like the [Hamiltonian_path_problem]
+- even when the input is required to be a [bipartite_graph], or even a [grid_graph], cf [itai1982hamilton]
[Approximation] algorithm: [christofides_heuristic]
diff --git a/hamiltonian_path b/hamiltonian_path
@@ -6,6 +6,8 @@ A graph that has such a path is a [Hamiltonian_graph]
[Computational_problem]: [Hamiltonian_path_problem]
-See also: [hamiltonian_cycle], [traveling_salesperson_problem], [k_path], [path_length], [eulerian_path], [3_hamiltonian_path]
+See also: [hamiltonian_cycle], [traveling_salesperson_problem], [k_path], [path_length], [eulerian_path], [3_hamiltonian_path], [edge_hamiltonian_path]
Up: [path]
+
+Aliases: hamiltonian paths
diff --git a/hamiltonian_path_problem b/hamiltonian_path_problem
@@ -2,9 +2,11 @@
The [computational_problem] of [deciding] whether an input [undirected_graph] is a [Hamiltonian_graph], i.e., has a [hamiltonian_path]
-It is [np_complete], but it is [FPT] [parameterized] by [treewidth]:
+It is [NP_complete], but it is [FPT] [parameterized] by [treewidth]:
- https://cs.stackexchange.com/questions/59325/an-fpt-algorithm-for-hamiltonian-cycle-running-parameterized-by-treewidth
+It is [NP_complete] even when the input is required to be a [bipartite_graph], or even a [grid_graph], cf [itai1982hamilton]
+
Up: [decision_problem], [hamiltonian_path]
See also: [Hamiltonian_cycle_problem]
diff --git a/line_graph b/line_graph
@@ -6,7 +6,8 @@ The *line graph* of an [undirected_graph] G = (V, E) is the [graph] G' where the
They can be recognized in [linear_time]
-They have a [Hamiltonian_cycle] if the original graph has a [Hamiltonian_cycle]: cf [balakrishnan2012textbook], Corollary 6.5.5 and [harary1965eulerian]
+- For [hamiltonian_cycles], cf [edge_hamiltonian_cycle]
+- For [hamiltonian_paths], cf [edge_hamiltonian_path]
The [graph_square] of the line graph, and the line graph of the [graph_square], are essentially always [Hamiltonian] for [connected_graphs], cf [nebesky1973line]
diff --git a/longest_common_substring b/longest_common_substring
@@ -6,6 +6,6 @@ Can be solved in [linear_time] with a [suffix_tree]
Up: [stringology], [subword]
-See also: [longest_common_subsequence]
+See also: [longest_common_subsequence], [substring_distance]
-Aliases: longest common factor, longest common infix
+Aliases: longest common factor, longest common infix, longest common subword
diff --git a/string_distance b/string_distance
@@ -4,6 +4,7 @@
- [levenshtein_distance]
- [hamming_distance]
- [dynamic_time_warping]
+- [substring_distance]
Up: [distance] on [string]
diff --git a/substring_complexity b/substring_complexity
@@ -6,4 +6,4 @@ The *substring complexity* of a [word] s for an integer k is its number of disti
Up: [compression_string]
-See also: [Simons_congruence]
+See also: [Simons_congruence], [substring]
diff --git a/substring_distance b/substring_distance
@@ -0,0 +1,11 @@
+# Substring distance
+
+Defined in [ng2017state], also called "subword distance" in [choffrut2002distances]
+
+Called "push pop distance" in [amarilli2023enumerating]
+
+Up: [subword], [string_distance]
+
+Aliases: subword distance, push pop distance
+
+See also: [edit_distance], [longest_common_substring]
diff --git a/subword b/subword
@@ -14,8 +14,10 @@ must be contiguous, unlike [subsequence]
- [subword_closure]
+- [substring_distance]
+
Up: [formal_language_theory]
See also: [language_downwards_closed], [subword_universal], [factor], [compressed_subword_problem], [subsequence_order]
-Aliases: subwords
+Aliases: subwords, substring, substrings
