cycle_rank (746B)
1 # Cycle rank 2 3 https://en.wikipedia.org/wiki/Cycle_rank 4 5 The *cycle rank* of a [DAG] is 0 6 7 The *cycle rank* of a [directed_graph] which is not [strongly_connected_graph] is the [maximum] of the cycle rank of the [SCCs] 8 9 The *cycle rank* of a [strongly_connected_graph] is 1 plus the [minimum] across all [vertices] v of the cycle rank of the [graph] obtained by [vertex_deletion] of v 10 11 It is a kind of analogue of [tree_depth] but for [directed_graphs] instead of [undirected_graphs] 12 13 The [computational_problem] of computing cycle rank is [NP_hard] 14 15 See also: [feedback_edge_number], [pathwidth_directed], [treewidth_directed], [circuit_rank], [strahler_number], [star_height], [eggans_theorem], [cycle] 16 17 Up: [width_measure] for [directed_graph]