commit 400d079b4b646cdf81bd414f4c315a8402077c9d
parent f377ef369f5d55b60c7bfb26b79d5a7e1970bce3
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 12 Dec 2025 12:50:14 +0100
Merge remote-tracking branch 'origin/master'
Diffstat:
15 files changed, 47 insertions(+), 8 deletions(-)
diff --git a/algorithms b/algorithms
@@ -9,6 +9,7 @@ Type:
- [algorithm_randomized]
- [greedy_algorithm]
- [graph_algorithms]
+- [counting_algorithm]
- [text_algorithms]
By date:
diff --git a/circuit b/circuit
@@ -59,6 +59,6 @@
Up: [theoretical_computer_science]
-See also: [sum_product_network], [formula]
+See also: [sum_product_network], [formula], [cycle_circuit]
Aliases: circuits
diff --git a/circuit_lower_bound b/circuit_lower_bound
@@ -2,4 +2,11 @@
best known bound on an explicit function: [find2015better], (3+1/86)n - o(n) lower bound on the size of [boolean_circuit] for a [boolean_function]
+- [SDNNF_lower_bounds]
+- [DNNF_lower_bounds]
+- [dSDNNF_lower_bounds]
+- [dDNNF_lower_bounds]
+
Up: [circuit_size]
+
+Aliases: circuit lower bounds
diff --git a/counting_algorithm b/counting_algorithm
@@ -0,0 +1,7 @@
+# Counting algorithm
+
+An [algorithm] for a [counting_problem]
+
+- [BEST_theorem]
+
+Up: [algorithms], [counting_problem]
diff --git a/counting_problem b/counting_problem
@@ -20,3 +20,5 @@
Up: [computational_problem], [counting]
Aliases: counting problems
+
+See also: [counting_algorithm]
diff --git a/cycle b/cycle
@@ -7,7 +7,7 @@ In [undirected_graphs], cycles are typically required to have length at least 3
In [directed_graphs], we have [directed_cycles]
Variants:
-- [circuit_(graph)] if the same [vertices] (but not [edges]) can be visited multiple times
+- [cycle_circuit] if the same [vertices] (but not [edges]) can be visited multiple times
- like a [trail] compared to a [simple_path]
- [tour] if the same [vertices] and [edges] can be visited multiple times
- like a [walk] compared to a [simple_path]
diff --git a/ddnnf b/ddnnf
@@ -4,6 +4,8 @@
[circuit_equivalence_problem]: [circuit_equivalence_dDNNFs]
+- [dDNNF_lower_bounds]
+
Up: [knowledge_compilation_classes], [dd]
See also: [dnnf], [decision_dnnf], [uobdd], [times_uplus_circuit]
diff --git a/dnnf b/dnnf
@@ -14,6 +14,8 @@ Special cases:
Compilation of DNNFs to [conjunctive_normal_form] cannot be done tractably because DNNFs include [DNFs]
+- [DNNF_lower_bounds]
+
See also: [ddnnf], [decision_dnnf], [times_cup_circuit]
Up: [knowledge_compilation_classes]
diff --git a/dsdnnf b/dsdnnf
@@ -4,6 +4,8 @@
not closed under [complementation], cf [vinallsmeeth2024structured] by [harry]
+- [dSDNNF_lower_bounds]
+
Up: [knowledge_compilation_classes], [ddnnf], [sdnnf]
Aliases: dSDNNFs, d_SDNNFs, d_SDNNF
diff --git a/eulerian_circuit b/eulerian_circuit
@@ -0,0 +1,9 @@
+# Eulerian circuit
+
+An [Eulerian_path] which is a [cycle_circuit], i.e., starts and ends at the same [vertex]
+
+The number of Eulerian circuits in [directed_graphs] can be computed in [PTIME] by the [BEST_theorem]
+
+Up: [eulerian_path]
+
+Aliases: Eulerian cycle
diff --git a/eulerian_cycle b/eulerian_cycle
@@ -1,5 +0,0 @@
-# Eulerian cycle
-
-An [Eulerian_path] which is a [cycle], i.e., starts and ends at the same [vertex]
-
-Up: [eulerian_path]
diff --git a/induced_matching b/induced_matching
@@ -0,0 +1,9 @@
+# Induced matching
+
+A [matching] which is an [induced_subgraph]
+
+Given a [graph], it is [NP_hard] to find a [maximum_induced_matching]
+
+Up: [matching], [induced_subgraph]
+
+See also: [mim_width]
diff --git a/matching b/matching
@@ -17,6 +17,7 @@ Algorithms [graph_algorithm]:
Variants:
- [matching_variants]
+- [induced_matching]
- [exact_matching]
Also the [linear_relaxation]: see [fractional_edge_packing]
diff --git a/sdnnf b/sdnnf
@@ -2,6 +2,8 @@
like [DNNFs] but [structured]
+- [SDNNF_lower_bounds]
+
Up: [knowledge_compilation_classes], [dnnf], [structuredness]
Aliases: SDNNFs
diff --git a/trail b/trail
@@ -4,6 +4,6 @@ A [walk] where [vertices] can repeat, but not [edges]
Up: [path]
-See also: [walk], [simple_path]
+See also: [walk], [simple_path], [cycle_circuit]
Aliases: trails
