Graph Algorithms: Assessment Highlights
A collection of graph problems that test deep understanding rather than memorization.
The Bridge Detection Variant
Find all edges whose removal increases the number of triangles in the graph.
Solution Approach
Counter-intuitively, we need to count triangles that share exactly one edge with the candidate. The algorithm runs in O(m√m) time using careful enumeration.
Shortest Path with Wildcards
Given a graph where some edge weights are variables, find assignments that minimize the longest shortest path.
Key Insight
This reduces to a linear programming problem with interesting structure. The dual interpretation reveals connections to network flow.
Teaching Through Problems
These problems help students see beyond standard algorithms to underlying principles.
Subscribe to our newsletter
Stay updated with the latest articles, tutorials, and insights from our team. We'll never spam your inbox.
By subscribing, you agree to our Privacy Policy and consent to receive updates from our company.