commit 01d6e24a1b3a2500237acc6afcc6e996817538f5
parent 899d90f2afd15fb9db55e7208771b6ca079c2674
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 23 Oct 2025 09:58:44 +0200
commit with codex
Diffstat:
5 files changed, 16 insertions(+), 4 deletions(-)
diff --git a/graph_cubic b/graph_cubic
@@ -2,6 +2,8 @@
A [graph] where the [degree] of each [vertex] is 3
+[Petersen's_theorem]: every cubic graph without [cut_edges] has a [perfect_matching], cf Theorem 16.14 of https://faculty.etsu.edu/gardnerr/5340/notes-Bondy-Murty-GT/Bondy-Murty-GT-16-4.pdf
+
Up: [maximal_degree]
Aliases: cubic graph, cubic graphs
diff --git a/longest_palindromic_subsequence b/longest_palindromic_subsequence
@@ -1,7 +1,8 @@
# Longest palindromic subsequence
Can be done in [quadratic_time] and [linear_memory]: reverse the string and find [longest_common_subsequence], cf https://www.geeksforgeeks.org/dsa/longest-palindromic-subsequence-dp-12/
+- beware of subtleties, cf [brodal2024finding]
Up: [computational_problem], [subsequence], [palindrome]
-See also: [longest_palindromic_factor]
+See also: [longest_palindromic_factor], [LCS]
diff --git a/nae3sat b/nae3sat
@@ -2,4 +2,4 @@
https://en.wikipedia.org/wiki/Not-all-equal_3-satisfiability
-Up: [sat_variants]
+Up: [sat_variants], [NAESAT]
diff --git a/perfect_matching b/perfect_matching
@@ -2,12 +2,12 @@
A [matching] where every vertex is incident to an edge of the matching
-- [minimum_perfect_matching] / [hungarian_algorithm]
+- [maximum_perfect_matching] / [hungarian_algorithm]
- [perfect_matching_counting]
Up: [matching]
-See also: [matching_counting]
+See also: [matching_counting], [f_factor]
Aliases: perfect matchings
diff --git a/xsat b/xsat
@@ -0,0 +1,9 @@
+# XSAT
+
+A [Boolean_satisfiability_problem] formed as a [conjunction] of [clauses], in each clause precisely one [literal] must be true
+
+Also called "1-in-3-SAT" in the case of [3SAT]
+
+Up: [sat_variants]
+
+See also: [exact_cover], [hitting_set]
