depth. At each level of the recursion, only linear workis needed to identify the separators as well as the connections possible betweenvertices. The overall result is preprocessing time with only additional information stored for each vertex.

Kameda's Algorithm

An even faster method for pre-processing, due to T. Kameda in 1975,can be used if the graph is planar, acyclic, and also exhibits the following additional properties: all 0-indegree

1.Previous
3.Next