Encoding cds_decision.gringo

Name	cds_decision.gringo
Class Tree	[Root] Graph Problems (32) Connected Dominating Set (1)
Submitter	Martin Gebser
Author	Martin Gebser and Roland Kaminski
Description	A Gringo encoding of the Connected Dominating Set problem.
Created	2009-03-12 16:33
Modified	2009-03-12 16:36
Languages	Gringo 2.0.2
Language Features	Cardinality constraints Choice rules
Compatible Instance Classes	Connected Dominating Set
Input Predicates	bound/1 edge/2 vtx/1
Output Predicates	dom/1
Encoding Parameter
Standalone	No
Tags	ASP Contest 09 (Martin Gebser)
Attributes
Content	#hide. #show dom/1. % select the dominating set { dom(U) : vtx(U) }. % normalize graph uedge(U,V) :- edge(U,V), U < V. uedge(U,V) :- edge(V,U), U < V. % vertex V has an edge in the set D or is in D in(V) :- uedge(U,V), dom(U). in(V) :- uedge(V,U), dom(U). in(V) :- dom(V). % build reachability relation reach(U) :- dom(U), not dom(V) : vtx(V) : V < U. reach(V) :- reach(U), dom(V), uedge(U,V). reach(V) :- reach(U), dom(V), uedge(V,U). % dominating set conditions :- dom(U), not reach(U). :- vtx(U), not in(U). :- not { dom(U) : vtx(U) } K, bound(K).

Actions