Information Technology Reference
In-Depth Information
Proposition 2.
An elementary circuit in the distance graph of a flooding prob-
lem is negative if and only if it includes a negative path
{i,
0
,j}
.
To find all the conflicts, we have to enumerate all the pairs (
i, j
) of vertices
involved in a negative path
{i,
0
,j}
and check existence of an elementary path
from
j
to
i
which does not include the vertex 0. The complexity of the conflict
detection procedure is
O
(
n
2
e
)intheworstcase.
3.2
Representation of the Conflicts
We recall that we are interested in revising estimates on water heights in the
parcels. Each conflict between the constraints
l
i
≤ X
i
− X
0
and
X
j
− X
0
≤ u
j
is
represented by the tuple (
i, j, u
j
− l
i
) . The set of conflicts is represented by the
graph
G
c
=(
V, E
).
V
is the set of vertices
V
=
,where
Low
i
(respectively
Upp
i
) corresponds to the constraint
l
i
≤ X
i
−X
0
(respectively
to the constraint
X
i
− X
0
≤ u
i
). Each conflict (
i, j, u
j
− l
i
) is represented by the
edge (
Low
i
,Upp
j
).
G
c
is called the
graph of conflicts
.
{Low
i
,Upp
i
:1
≤ i ≤ n}
3.3
Computing a Subset of Constraints to Correct
To remove all the detected conflicts, some constraints involved in them have to
be revised. We have to look for a subset of constraints whose the revision is
sucient to restore the consistency. A minimal revision of the problem needs to
find a minimal subset of constraints whose the correction restores the consistency.
This amounts to find a minimal vertex cover of the conflict graph.
Looking for a vertex cover of a fixed size is an NP-Complete problem [2], and
looking for minimal vertex covers is NP-Hard.
To compute a minimal vertex cover of the graph of conflicts, we use the
Minimal-Cover
algorithm (see [4] for details) whose complexity is
O
(
n
c
2
n
c
)in
the worst case, where
n
c
is the number of vertices of the conflict graph.
Another alternative is to consider a ”good” vertex cover rather than a mini-
mal one. Such cover is computed by the
Good-Cover
algorithm (see [4] for details)
which consider only the vertices of highest degree in the graph of conflicts. The
complexity of the
Good-cover
algorithm is
O
(
n
c
)intheworstcase.
3.4
Revision of the Conflicting Constraints
We shall see now, how to perform the corrections. Let (
i, j, u
j
− l
i
) be a conflict
between the constraint
l
i
≤ X
i
− X
0
and the constraint
X
j
− X
0
≤ u
j
.The
elimination of this conflict needs the revision of one of these constraints. The
following proposition states how this operation is done.
Proposition 3.
Let
c
=(
i, j, u
j
− l
i
)
be a conflict between the constraints
X
j
− X
0
≤ u
j
and
l
i
≤ X
i
− X
0
. Replacing the constraint
X
j
− X
0
≤ u
j
(respec-
tively, the constraint
l
i
≤ X
i
− X
0
) by the constraint
X
j
− X
0
≤ l
i
(respectively,
the constraint
u
j
≤ X
i
− X
0
)correctstheconflict
c
.
Search WWH ::
Custom Search