CSC 482B/582B Assignment 1 Part A: Literature Review

Learning objectives: an introduction to preparing a paper in LaTeX that includes a bilbilography. Click here for some hints on how to use latex.

A subset S of the vertices of a graph G is called a dominating set if every vertex v of G is either in S or v has a neighbour which is in S (that is, there is some vertex u in S such that (u, v) is an edge of G). A connected dominating set S is a dominating set such that the subgraph of G induced by S is connected.

Find some interesting papers on the subject of connected dominating set by searching on Mathscinet.

CSC 482B students: 4 papers.

CSC 582B students: 6 papers.

If you think you might change from CSC 482B to CSC 582B: 6 papers.

On connex (as an attachment to Assignment #1 Part A) there is a class list that assigns a digit between 0-9 to each student. This list is the same as the one I brought to class. To minimize having students choosing the same papers, you are required to select papers whose math review number has last digit equal to the digit you have been assigned.

Start out your paper by defining the connected dominating set problem (begin by defining a graph and define all terms you include). Then write a very short survey paper using LaTeX that gives a brief description of the contents of each of your chosen papers (about 3-4 sentences for each one).

Some points to address:

1. If the paper considers a specific class of graphs (e.g. planar graphs), what class is considered? Define that class of graphs.
2. If the paper is an algorithm, what type of algorithm is it? Is it an exact algorithm (guaranteed to find an optimal solution)? Is it a heuristic (finds good solutions with no guarantee they are optimal)? Is it an approximation algorithm (gives a gurantee on quality of the solution such as being at most twice as big as an optimal solution)?
3. For an algorithm, how did they evaluate its performance? Using a Big Oh type of analysis? By comparing running times to that of other algorithms?
4. I am especially interested in any classes of graphs for which a minimum connected dominating set is known for some cases but not for others. In this case, what are the smallest open cases?

I do not expect you to read the papers and digest every detail. Start by reading the abstract, introduction and conclusions. Scan the rest of the paper quickly.

What you should submit under connex for Assignment 1A:

1. The files used to prepare your paper: please name these as LastName.tex and LastName.bib.
   For example: I would use Myrvold.tex and Myrvold.bib
2. The pdf copies of the 4 papers you survey for CSC 482 or 6 papers you survey for CSC 582. If you find a reference to an interesting paper but cannot easily get the pdf for it, choose some other paper to survey instead.
3. The typeset paper: LastName.pdf For example, I would use Myrvold.pdf.
   Your name (but not your ID number) should be included in the typeset paper as the author of the paper.