CSC 422 Literature Review Project: Summer 2017

The literature review is due on Fri. June 23 at 11:55pm.

Students who exceed expectations can get bonus marks.

Survey Paper

The aim of this paper is to survey algorithms and open problems for the dominating set problem and some of its variants. Your survey paper should be written using LaTeX.

VERY IMPORTANT: Please use at least a 12 point font and 1.5 spacing for your submissions. The sample LaTeX has the commands you need to do this.
Please click here to see some sample LaTeX.
Put your name on the paper but DO NOT include your student ID number. Upload at least three files to connex (.tex, .bib and .pdf), plus any other files used to create your paper (e.g. pictures). Use your name as part of the file names. For example, I might upload:

1. Myrvold.tex (my survey paper)
2. Myrvold.bib (my references for the topic, possibly including a small number related to the topic that you decide to not reference in your paper).
3. Myrvold.pdf (what I get after typesetting)
4. Myrvold_8dodec.eps (a picture I use in the paper).

You should write your paper in your own words. Copying and pasting sentences or paragraphs that someone else has written is plagiarism and will be penalized with a mark of 0 on this project. Extreme cases (copying large blocks of text) could be penalized with a failure in the class. It is highly desirable to use standard definitions instead of trying to make up new ones in your own words. But otherwise, if you copy a phrase or sentence it should be in quotes and attributed to the original author. If you restate the ideas of another author in your own words, you should reference the author but quotes are not required.

Papers should be written in sentence/paragraph format in the same style as a journal or conference paper. Terms should be defined before they are first used.

Conferences and journals vary widely in terms of the quality of their submissions. One place you can find ratings of them is: Computing research and education portal (Core).

In your .bib file, include a notes field for each paper indicating its quality as per this list. For example:
note= {Quality A*.},
or for journals or conferences not indexed:
note= {Quality unranked.},

For each paper you are asked to survey, include a paragraph (or two) describing the main results.

You can reference materials you find on the web but these references are in addition to the ones required to get full marks for your survey. If you are looking for papers in Congressus Numerantium, I have many issues in my office- please ask me about them.

1. [5] Define an undirected graph.
2. [5] Define the dominating set problem.
3. [5] Define the independent dominating set problem.
4. [5] Define the connected dominating set problem.
5. [10] Give an illustrative example of a graph that has different sized optimal solutions for dominating set, independent dominating set and connected dominating set. For full marks include a picture of your graph.
6. [10] Give precise descriptions of two different types of applications for where one of these graph theory problems has been used to model a problem in some other domain. For each one, include one journal/conference paper reference.
7. [5] Define a covering code and explain the connection between covering codes and the dominating set problem.
8. [50] Survey 5 papers that describe algorithms for one of these problems. Your 5 papers should include at least one from each category:
   1. An exact algorithm.
   2. A heuristic approach.
   3. An approximation algorithm.
   4. An algorithm used for finding covering codes.
   5. An algorithm for a special class of graphs.
9. [5] Define Vizing's conjecture.
10. [10] Vizing's conjecture is an interesting open problem for dominating sets. Find at least two papers that are not surveys that give results on Vizing's conjecture. In particular, I am especially interested in knowing about classes of graphs where the conjecture is known to be true, or characterizations of graph classes that could include a counterexample.

Bonus marks: You can skip this part and still get 100% on this paper.

1. Survey more than the required number of papers.
2. Identify graphs or classes of graphs where the dominating set problem is an open question, and survey what is known (for example, is there a lower bound and upper bound on the answer for the graph(s) in question?). Note: many of these results are in papers about covering codes.