commit 40a0b6daddf43dea4990592033c67ead56d7d33e
parent 0e7c23954a729dabcc60581f406036f7d22712b2
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 23 Mar 2025 18:09:23 +0100
commit with codex
Diffstat:
3 files changed, 8 insertions(+), 2 deletions(-)
diff --git a/circuit_rank b/circuit_rank
@@ -2,6 +2,8 @@
https://en.wikipedia.org/wiki/Circuit_rank
+[computational_problem] of computing circuit rank: can be done in [linear_time] by computing any [spanning_forest]
+
See also: [feedback_edge_number], [cycle_rank]
Up: [width_measure]
diff --git a/feedback_edge_number b/feedback_edge_number
@@ -4,6 +4,10 @@ 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]
+
See also: [feedback_vertex_set], [feedback_vertex_number], [circuit_rank], [cycle_rank]
Up: [width_measure]
diff --git a/spanning_tree b/spanning_tree
@@ -3,8 +3,8 @@
- [minimum_spanning_tree]
- [minimum_degree_spanning_tree]
-See also: [steiner_tree]
+See also: [steiner_tree], [spanning_forest]
-Up: [tree]
+Up: [tree], [subgraph]
Aliases: spanning trees
