| Question asked
|
The conclusion of time complexity O(G*exp) … The conclusion of time complexity O(G*exp) seems to be based on the assumption that each call to Label does some fraction of G*Di(exp) work. However, accounting for lines 5-6 of Label seems less intuitive as the proof for theorem one states only that a depth-first search could be used. Generally, a depth-first search runs in O(V+E) time for a given graph G0=(V,E). V seems like it could be O(G*exp) (exp local to Label), but how do we account for E? Furthermore, do we have to run this depth-first search for every (u,q0) in the product automaton? Am I missing something? Is there some aspect of the nature of the product automaton that I'm overlooking? he product automaton that I'm overlooking?
|
