CIS 675: Algorthms – Spring 2019
Homework 8

Version 1   (13 March 2019)


Abbreviations


Reading


Notation


Problems

  1. (24 points) PG Problems 392, 393, 394. Each part is 8 points.

  2. (26 points) DPV, Problem 6.11.

  3. (26 points) DPV, Problem 6.18.
  4. (24 points) DPV. Problem 6.21.
    1. (8 points) Show that if U is an independent set, then (V-U) is a vertex cover.
    2. (8 points) Show that if U is a vertex cover, then (V-U) is an independent set.
    3. (8 points) Show how to use the algorithm of section 6.7 to solve this problem.