commit 51c5742559f6c07441fc35abd2107f56def2a116
parent 6c9b55868b5ddb1f5ac5439b13b4cf06bd8bd2fa
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 15 May 2026 21:03:47 +0200
Merge remote-tracking branch 'origin/master'
Diffstat:
13 files changed, 39 insertions(+), 8 deletions(-)
diff --git a/2sat b/2sat
@@ -13,4 +13,4 @@ However:
See also: [3sat], [Max_2sat]
-Up: [sat_variants]
+Up: [k_SAT]
diff --git a/3sat b/3sat
@@ -6,7 +6,7 @@ It is [np_complete]
[3sat_variants]
-Up: [sat_variants]
+Up: [k_SAT]
See also: [2sat], [schaefers_dichotomy_theorem]
diff --git a/automaton_emptiness b/automaton_emptiness
@@ -4,4 +4,4 @@ It is [nl_complete] to check [automaton] emptiness
Up: [automata_problems], [language_emptiness]
-See also: [automaton_finiteness], [universality_automata], [intersection_nonemptiness]
+See also: [automaton_finiteness], [universality_automata], [intersection_nonemptiness], [automaton_nonemptiness]
diff --git a/edge_coloring b/edge_coloring
@@ -1,8 +1,18 @@
# Edge coloring
+A function mapping the [edges] of an [undirected_graph] to colors such that no two incident edges get the same color
+
+An easy lower bound on the number of colors required is the [maximum_degree]
+
+[Vizings_theorem]: the number of colors needed is always at most the [maximum_degree] plus one
+
+It is [NP_hard] to determine which of the two applies
+
+Computing edge colorings whose number of colors is the [maximum_degree] plus one can now be done in [near_linear_time]
+
- [incremental_maintenance_edge_coloring]
-- [vizings_theorem]
- [2_edge_coloring]
+- [online_edge_coloring]
Up: [graph_coloring]
diff --git a/exponentiation b/exponentiation
@@ -9,4 +9,4 @@ Up: [mathematics_operation]
See also: [exptime], [semigroup], [multiplication], [power_mathematics], [square_root]
-Aliases: exponent, exponents
+Aliases: exponent, exponents, exponential, exponentials
diff --git a/graph_modification_problem b/graph_modification_problem
@@ -5,6 +5,8 @@
- for [treewidth]: [graph_modification_treewidth]
+- [graph_deletion_problem]
+
Up: [graph_modification]
Aliases: graph modification problems
diff --git a/graph_modification_treewidth b/graph_modification_treewidth
@@ -2,4 +2,4 @@
- reducing [treewidth] by removing [graph] [edges]: [marchand2022tree]
-Up: [treewidth], [graph_modification]
+Up: [treewidth], [graph_deletion]
diff --git a/k_sat b/k_sat
@@ -0,0 +1,8 @@
+# K SAT
+
+[SAT] but with [CNFs] of [clause_width] at most k
+
+- [2SAT]
+- [3SAT]
+
+Up: [sat_variants]
diff --git a/maximal_degree b/maximal_degree
@@ -10,3 +10,5 @@ Special cases:
- see also [cubic_graph], where the degree of each vertex is 3
Up: [degree], [maximum]
+
+Aliases: maximum degree
diff --git a/query_resilience b/query_resilience
@@ -1,4 +1,4 @@
-# Resilience
+# Query resilience
The *resilience* of a [query] Q on a [database] D is the minimal number of [tuples] to be deleted from D so that Q is not satisfied:
- can be 0 if Q is false on D
diff --git a/t_odd_orientation b/t_odd_orientation
@@ -2,6 +2,6 @@
Given an [undirected_graph] G and subset T of vertices, a *T-odd orientation* is a [graph_orientation] of G where precisely the vertices of T have odd [in_degree]
-discussed in [gravier2025note] in connection to [acyclic_orientation]
+discussed in [gravier2025note] in connection to [acyclic_orientation], also in [gravier2026some]
Up: [graph_orientation]
diff --git a/twin_width b/twin_width
@@ -23,6 +23,8 @@ guarantees that [first_order_model_checking_parameterized_complexity] is [fixed_
[twin_width_ordered]
+[twin_width_computation]
+
Up: [width_measure]
See also: [nowhere_dense], [merge_width]
diff --git a/unique_ov b/unique_ov
@@ -0,0 +1,7 @@
+# Unique OV
+
+studied in [ball2017average]
+
+Up: [orthogonal_vectors]
+
+See also: [unique_k_SAT]
