Next: The Exploring Process and Up: The Search Method Previous: Deleting Edges

## The Operators

Although the previous description of the operators that define the neighborhood of an RPDAG is quite convenient from a practical (implementation) point of view, for the sake of clarity, we shall describe them in another way. In fact, we shall use five operators:

• , addition of an arc .
• , deletion of an arc .
• , deletion of a link .
• , addition of an arc and creation of the h-h pattern by transforming the link into the arc .

The conditions that the current RPDAG must verify so that each of these operators can be applied in order to obtain a valid neighboring RPDAG are shown in Table 2. These conditions can be easily derived from the information in Figure 10 and Table 1. In Table 2, represents a test for detecting completely undirected cycles after inserting the link in the current RPDAG. Note that we can perform this test very easily without actually inserting the link: it is only necessary to check the existence of a path between and exclusively formed by the links. Similarly, and represent tests for detecting directed cycles after inserting the arc and the h-h pattern in the current RPDAG, respectively (and perhaps completing). It should also be noted that we can perform these tests without inserting the arc or the h-h pattern: in this case we only need to check the existence of a path from to containing only either links or arcs directed away from (a partially directed path from to ). Table 2 also shows which operators may require a post-processing step in order to ensure that the corresponding neighboring configuration of is an RPDAG. In Table 2, and refer to the procedures that preserve conditions 1 and 4 in Definition 1, respectively. Note that both and take time in the worst case, where is the number of links in the subgraph induced by the chain component of that contains ; takes time in the worst case, where is the number of arcs in the subgraph induced by the set of descendants of in that only have one parent; and both take time in the worst case, where is the number of edges (either arcs or links) in the subgraph induced by the nodes in the chain component of that contains together with their descendants.

Table 2: The operators, their conditions of applicability, and post-processing requirements
 Operator Conditions Post-processing ; or ; if if then then ; and ; if None then if then None ; ; and ; if if ) then then

Next: The Exploring Process and Up: The Search Method Previous: Deleting Edges
Luis Miguel de Campos Ibáñez 2003-05-30