 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

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. Disclaimer / Datenschutzerklärung