commit 474a46242ab807248a3aa9e8f9f382ed65f5c260
parent 948f7470ff2ec656ae6ce6e7ae59bdb059927d14
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 24 Jun 2025 17:45:59 +0200
commit with codex
Diffstat:
4 files changed, 34 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
