commit 4fb8794d0cc093c3e7a6a8b1b1fb6eb5bb4ef7c2
parent ded33c5ef61ce2f173eea874b035480a91652140
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 11 Dec 2025 23:26:46 +0100
commit with codex
Diffstat:
10 files changed, 32 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/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/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/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
