It's UWAweek 39 (2nd semester, week 9)

help3001

This forum is provided to promote discussion amongst students enrolled in CITS3001 Algorithms, Agents and Artificial Intelligence.

Please consider offering answers and suggestions to help other students! And if you fix a problem by following a suggestion here, it would be great if other interested students could see a short "Great, fixed it!"  followup message.

How do I ask a good question?
Displaying selected article
Showing 1 of 158 articles.
Currently no other people reading this forum.


 UWA week 31 (2nd semester, week 2) ↓
SVG not supported

Login to reply

👍x2
helpful
8:29pm Tue 1st Aug, ANONYMOUS

Both problems require you to find a minimal subset of the vertices satisfying some covering condition. However, the difference is that the vertex cover problem requires you to cover all the edges, whereas the the dominating set problem requires you to cover all the vertices. To clarify what "cover" means, an edge is covered iff at least one of the edge's 2 vertices is in the set, and a vertex is covered iff it is in the subset or if it neighbours a vertex which is in the subset. For an example, see the attached image (stolen from the slides). All of the vertices are covered since each of the vertices have a neighbour in the subset (the vertices coloured black). On the other hand, the edges aren't all covered since the "bottom" edges do not have any of their vertices in the subset.



This article has 1 attachment:

 

The University of Western Australia

Computer Science and Software Engineering

CRICOS Code: 00126G
Written by [email protected]
Powered by history
Feedback always welcome - it makes our software better!
Last modified  5:07AM Sep 06 2023
Privacy policy