You are given a directed graph G = (V, E) representing some financial choices. E

Question

You are given a directed graph G = (V, E) representing some financial choices. Each edge (u, v) epsilon E has a weight w(u, v), where w(u, v) > 0 represents a cost, and w(u, v) 0, or a profit -w(u, v) otherwise. We say that a vertex s is super-lucky if s itself is part of a cycle C of negative weight, so that starting from s one can repeatedly come back to s with some profit. Using the "matrix multiplication" approach, design O(n3log n) algorithm to find all super-lucky vertices. Say that s is lucky if there exists a way to eventually make unbounded profit starting from.s (but not necessarily coming back to s infinitely many times as with super-lucky vertices). Give the fastest algorithm you can for finding all lucky vertices (from scratch, without assuming you already solved part (a)). Solve the same problem as in part (b), but assuming somebody already gave you for free the list of all super-luck)' vertices (or, alternatively, you already ran your solution in part (a), and want to use it to compute lucky vertices faster). Namely, give the fastest algorithm you can think of for finding all lucky vertices given all super-lucky vertices. (Hint: Make sure you use super-lucky vertices instead of computing from scratch!) Assume s is not lucky (and, hence, not super-lucky). Design a fast algorithm to compute the best finite "financial strategy" to make as much profit starting from s as possible. State the running time of your algorithm. (Hint: Think Bellman-Ford.)

Explanation / Answer

answer in progress

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.