wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

feedback_edge_number (423B)


      1 # Feedback edge number
      2 
      3 minimum number of edges to remove ([feedback_edge_set]) to destroy all cycles
      4 
      5 usually posed for [graph_directed]; for [graph_undirected] see [circuit_rank]
      6 
      7 [computational_problem] of computing feedback edge number:
      8 - [NP_complete] by [reduction] from [vertex_cover_problem]
      9 - [APX_hard]
     10 
     11 See also: [feedback_vertex_set], [feedback_vertex_number], [circuit_rank], [cycle_rank]
     12 
     13 Up: [width_measure]