1.5.11 Feedback Edge/Vertex Set

Problem Input | Problem Output

INPUT                    OUTPUT

Input Description: A (directed) graph G=(V,E) .

Problem: What is the smallest set of edges E' or vertices V' whose deletion leaves an acyclic graph?


  • The Stanford GraphBase (C) (rating 4)

    Related Problems

  • Bandwidth Reduction
  • Job Scheduling
  • Topological Sorting

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .