wiki_research

commit 239853c863810205d2b031a8a7026332136a63e4
parent 5b4459b4335bf44ea26145e9bcea90a6fe7d01f3
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Sat, 22 Aug 2026 15:47:22 +0200

commit with codex

Diffstat:
2_hamiltonian_path
 | 
7
+++++++
3_hamiltonian_path
 | 
9
+++++++++
boolean_function_evasive
 | 
9
+++++++++
fbdd
 | 
5
+++++
graph_cube
 | 
2
+-
graph_square_hamiltonian
 | 
4
++--
hamiltonian_cycle_multiple
 | 
2
++
hamiltonian_path
 | 
4
+++-
obdd
 | 
5
++---
repair_notions
 | 
1
+
single_source_shortest_path_faster
 | 
2
++
ufbdd
 | 
7
+++++++

12 files changed, 50 insertions(+), 7 deletions(-)
diff --git a/2_hamiltonian_path b/2_hamiltonian_path
@@ -0,0 +1,7 @@
+# 2 hamiltonian path
+
+A [hamiltonian_path] of the [graph_square] of an [undirected_graph]
+
+Up: [hamiltonian_path]
+
+See also: [3_hamiltonian_path], [graph_square_hamiltonian], [2_hamiltonian_cycle]
diff --git a/3_hamiltonian_path b/3_hamiltonian_path
@@ -0,0 +1,9 @@
+# 3 hamiltonian path
+
+A [hamiltonian_path] of the [graph_cube] of an [undirected_graph]
+
+It always exists if the [graph] is [connected_graph]
+
+Up: [hamiltonian_path]
+
+See also: [2_hamiltonian_path], [3_hamiltonian_cycle]
diff --git a/boolean_function_evasive b/boolean_function_evasive
@@ -0,0 +1,9 @@
+# Evasive Boolean function
+
+https://en.wikipedia.org/wiki/Evasive_Boolean_function
+
+A [boolean_function] where every [decision_tree] has height equal to the number of variables
+
+Up: [boolean_function_classes]
+
+Aliases: evasive Boolean function, evasive Boolean functions
diff --git a/fbdd b/fbdd
@@ -6,6 +6,11 @@ Is a subclass of [DNNF]
 
 Can be [circuit_negated] in [PTIME] by swapping the [sinks]
 
+Generalizations:
+
+- [uFBDD]
+- [nFBDD]
+
 Up: [bdd]
 
 Aliases: FBDDs
diff --git a/graph_cube b/graph_cube
@@ -4,4 +4,4 @@
 
 Up: [graph_exponentiation]
 
-See also: [graph_cubic]
+See also: [graph_cubic], [3_hamiltonian_path]
diff --git a/graph_square_hamiltonian b/graph_square_hamiltonian
@@ -1,9 +1,9 @@
 # Graph square hamiltonian
 
-An [undirected_graph] whose [graph_square] is a [Hamiltonian_graph]
+An [undirected_graph] whose [graph_square] is a [Hamiltonian_graph], i.e., G has a [2_hamiltonian_cycle]
 
 The [recognition_problem] is [NP_hard], cf [underground1978graphs]
 
 Up: [graph_square]
 
-See also: [graph_square_hamiltonian_variants]
+See also: [graph_square_hamiltonian_variants], [2_hamiltonian_cycle], [2_hamiltonian_path]
diff --git a/hamiltonian_cycle_multiple b/hamiltonian_cycle_multiple
@@ -6,3 +6,5 @@ A generalization of [Hamiltonian_cycle] where you can go over each [vertex] at m
 - mentioned here https://cstheory.stackexchange.com/questions/53492/name-for-a-cyclic-path-in-a-graph-that-visits-every-vertex-while-minimizing-the
 
 Up: [hamiltonian_cycle]
+
+See also: [hamiltonian_path_multiple]
diff --git a/hamiltonian_path b/hamiltonian_path
@@ -6,7 +6,9 @@ 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], [edge_hamiltonian_path]
+Variants: [3_hamiltonian_path], [hamiltonian_path_multiple]
+
+See also: [hamiltonian_cycle], [traveling_salesperson_problem], [k_path], [path_length], [eulerian_path], [edge_hamiltonian_path]
 
 Up: [path]
 
diff --git a/obdd b/obdd
@@ -2,13 +2,12 @@
 
 A [deterministic] [bdd] with a [variable_order]
 
-- [uobdd]
-- [nobdd]
-
 We can tractably take the [conjunction] and [disjunction] of two OBDDs where the [variable_order] is the same
 - [OBDD_conjunction]
 
 Generalizations:
+- [uOBDD]
+- [nOBDD]
 - [CFLOBDDs]
 - [FBDDs]
 
diff --git a/repair_notions b/repair_notions
@@ -4,6 +4,7 @@
 - [optimal_subset_repair], a [subset_repair] that [optimizes] a cost
 - can also do [insertions] of [tuples] in some cases
 - [minimal_repairs]
+- [cell_repairs]
 
 Up: [database_repairs]
 
diff --git a/single_source_shortest_path_faster b/single_source_shortest_path_faster
@@ -10,6 +10,8 @@ Solve [single_source_shortest_path] faster than [bellman_ford]
 recent result [bernstein2023negative] improving [bellman_ford]
 vs [lower_bounds] on [circuit_classes] for this problem [jukna2016optimality]
 
+also [li2026bellman] and [khanna2026n]
+
 Up: [single_source_shortest_path_algorithm]
 
 See also: [single_source_shortest_path_faster_nonnegative]
diff --git a/ufbdd b/ufbdd
@@ -0,0 +1,7 @@
+# UFBDD
+
+It is an [open_problem] whether they admit tractable [circuit_complementation], see [dDNNF_complementation]
+
+Up: [fBDD]
+
+See also: [uOBDD]