# Metadata Source URL:: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm Topics:: #mathematic, #programming --- # Topological sorting - Wikipedia ## Highlights > [!quote]+ Updated on 241022_140907 > > On a parallel random-access machine, a topological ordering can be constructed in O(log2 n) time using a polynomial number of processors, putting the problem into the complexity class NC2.[5] >One method for doing this is to repeatedly square the adjacency matrix of the given graph, logarithmically many times, using min-plus matrix multiplication with maximization in place of minimization. The resulting matrix describes the longest path distances in the graph. Sorting the vertices by the lengths of their longest incoming paths produces a topological ordering