Between O(nm) and O(nα)
Dieter Kratsch, Jeremy Spinrad · Symposium on Discrete Algorithms · 2003
This paper uses periodic matrix multiplication to improve the time complexities for a number of graph problems. The time for finding a clique cutset in a graph is reduced from O(nm) to O(n2.69), the time for finding an asteroidal triple is reduced to O(n2.82), and the time for finding a star cutset, a two-pair, and a dominating pair is reduced from O(nm) to O(n2.79).It is also shown that each of these problems is at least as hard as one of three basic graph problems for which the best known algorithms run in time O(nm) and O(nα).