Graph Theory37 sections · 1633 units
Open in CourseQuiz: Assignment Construction
Knowledge check
Check Your Understanding
After running SCC on a satisfiable -SAT instance, you pick the value for each variable based on topological order of SCCs. is in an SCC with higher topological number than . What value does get?
- A.True, because appears first in topological order
- B.True, because you always pick the positive literal
- C.False, because you set the literal in the later SCC to true, which is
- D.It depends on the other variables in the SCC