Perfect Matchings in d-regular Bipartite Graphs ( Random walks can also be used to design faster algorithms. Perfect Matchings in O(n log n)Time in Regular Bipartite Graphs,by Goel,Kapralov,Khanna Traditional:find augmenting paths by e.g.BFS/DFS Idea:replace BFS/DFS by a random walk (on a different Eulerian directed graph,i.e.indegree=outdegree for every vertex) Expected time to find an augmenting path =expected return time of the random walk =stationary distribution value Open research problem:Can you extend this to non-regular bipartite graphs? Perfect Matchings in d-regular Bipartite Graphs（选讲） Random walks can also be used to design faster algorithms. Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs, by Goel, Kapralov, Khanna • Traditional: find augmenting paths by e.g. BFS/DFS • Idea: replace BFS/DFS by a random walk (on a different Eulerian directed graph, i.e. indegree=outdegree for every vertex) • Expected time to find an augmenting path => expected return time of the random walk => stationary distribution value • Open research problem: Can you extend this to non-regular bipartite graphs?