wiki_research

commit 778342de660d882b3e19fbd14a7b59703557053a
parent 3e656e99f837f95fc9174676972c9fd6411aebc4
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue, 24 Jun 2025 22:50:42 +0200

Merge branch 'master' of a3nm.net:git/wiki_research

Diffstat:
bridge
 | 
9
+++++++++
feedback_edge_number
 | 
6
++----
feedback_edge_set
 | 
11
+++++++++++
minimum_feedback_edge_set
 | 
12
++++++++++++
regular_query
 | 
14
++++++++++++++

5 files changed, 48 insertions(+), 4 deletions(-)
diff --git a/bridge b/bridge
@@ -0,0 +1,9 @@
+# Bridge
+
+https://en.wikipedia.org/wiki/Bridge_(graph_theory)
+
+An [edge] of a graph whose [edge_removal] increases the number of [connected_components] of the [graph]
+
+See also: [graph_bridgeless], [bridge_set]
+
+Up: [edge]
diff --git a/feedback_edge_number b/feedback_edge_number
@@ -1,12 +1,10 @@
 # Feedback edge number
 
-minimum number of edges to remove ([feedback_edge_set]) to destroy all cycles
+minimum number of edges to remove ([feedback_edge_set]) to destroy all [cycles]
 
 usually posed for [graph_directed]; for [graph_undirected] see [circuit_rank]
 
-[computational_problem] of computing feedback edge number:
-- [NP_complete] by [reduction] from [vertex_cover_problem]
-- [APX_hard]
+[computational_problem] of computing feedback edge number: [minimum_feedback_edge_set]
 
 See also: [feedback_vertex_set], [feedback_vertex_number], [circuit_rank], [cycle_rank]
 
diff --git a/feedback_edge_set b/feedback_edge_set
@@ -0,0 +1,11 @@
+# Feedback edge set
+
+A set of [edges] in a [graph] whose [edge_removal] makes the [graph] an [acyclic_graph]
+
+- [feedback_edge_number]: minimal cardinality of a feedback edge set
+
+Up: [edge_set], [graph_theory]
+
+See also: [feedback_vertex_set]
+
+Aliases: feedback arc set
diff --git a/minimum_feedback_edge_set b/minimum_feedback_edge_set
@@ -0,0 +1,12 @@
+# Feedback edge number problem
+
+The [computational_problem] of computing the [feedback_edge_number] of a [graph]
+
+- [NP_complete] by [reduction] from [vertex_cover_problem]
+- [APX_hard]
+
+Up: [computational_problem], [feedback_edge_number]
+
+See also: [feedback_vertex_number_problem]
+
+Aliases: Feedback edge number problem
diff --git a/regular_query b/regular_query
@@ -0,0 +1,14 @@
+# Regular query
+
+A [CRPQ] whose atoms are themselves binary [CRPQs], and so recursively 
+
+Special cases:
+- [CRPQ]
+
+Generalizations:
+- [regular_queries_with_memory]
+- [Datalog]
+
+Studied in [reutter2017regular]
+
+Up: [query_language]