Path: DBAI > Research > Projects > D-FLAT Project > Software > D-FLAT System > Practice > Minimum Weighted Dominating Set
Tools: Print
Minimum Weighted Dominating Set
%dflat: --tables -e vertex -e edge -d td -n semi --default-join
%Extend table rows from child node.
1 { extend(R) : childRow(R,N) } 1 :- childNode(N).
% Retain relevant information.
item(in(X)) :- extend(R), not removed(X), childItem(R,in(X)).
auxItem(dominated(X)) :- extend(R), not removed(X),
childAuxItem(R,dominated(X)).
% Ensure that removed vertices are in the set or dominated.
:- extend(R), removed(X), not childItem(R,in(X)),
not childAuxItem(R,dominated(X)).
% Guess vertices into the dominating set.
{ item(in(X)) : introduced(X) }.
% A vertex is dominated if it is adjacent to a vertex in the set.
auxItem(dominated(Y)) :- item(in(X)), current(X;Y), edge(X,Y).
% Increment cost and current cost by number of newly introduced vertices.
counterInc(cost,W,X) :- introduced(X), item(in(X)), weight(X,W).
currentCounterInc(cost,W,X) :- introduced(X), item(in(X)), weight(X,W).
% Decrement cost by number of removed vertices.
currentCounterInc(cost,-W,X) :- extend(R), removed(X),
childItem(R,in(X)), weight(X,W).
#show item/1. #show auxItem/1. #show extend/1.
Last updated: 2017-08-30 17:51