It seems a natural lower bound of O(nm) on the flowproblem does not apply to Sleator-Tarjan as
I am not very sure about the reasons above. The latter is reasonably clear because of the amrotzed analysis, which treats is surely another way to treat the running time of the algorithm, but the former???
--
According to Spinrad et. al's book on graph classes, Yannakakis has shown a fundamental result about the total unimodularity of network matrices with no odd cycles (does sounds like some kind of bipartiteness?), and more importantly, gave a linear time recognition algorithm for the class.
To get the paper.
--
Have to get this book combinatorial-optimization: packing and covering. This book is supposed to be good.
--
A possible multi-dimensional search algorithm for the unitary PRDG: Create a d-dimensional tree and create a directed graph in each dimension. Now how can we make a cycle in a dimension effect another?
Posts
No comments:
Post a Comment