Maurice Tutor

(5)

$15/per page/Negotiable

About Maurice Tutor

Levels Tought:
Elementary,Middle School,High School,College,University,PHD

Expertise:
Algebra,Applied Sciences See all
Algebra,Applied Sciences,Biology,Calculus,Chemistry,Economics,English,Essay writing,Geography,Geology,Health & Medical,Physics,Science Hide all
Teaching Since: May 2017
Last Sign in: 406 Weeks Ago, 2 Days Ago
Questions Answered: 66690
Tutorials Posted: 66688

Education

  • MCS,PHD
    Argosy University/ Phoniex University/
    Nov-2005 - Oct-2011

Experience

  • Professor
    Phoniex University
    Oct-2001 - Nov-2016

Category > Computer Science Posted 17 Sep 2017 My Price 5.00

independent-set problem

Independent set

An independent set of a graph G = (V, E) is a subset V" ? V of vertices such that each edge in E is incident on at most one vertex in V". The independent-set problem is to find a maximumsize independent set inG.

a. Formulate a related decision problem for the independent-set problem, and prove that it is NP-complete. (Hint: Reduce from the clique problem.)

b. Suppose that you are given a "black-box" subroutine to solve the decision problem you defined in part (a). Give an algorithm to find an independent set of maximum size. The running time of your algorithm should be polynomial in |V| and |E|, where queries to the black box are counted as a single step.

Although the independent-set decision problem is NP-complete, certain special cases are polynomial-time solvable.

c. Give an efficient algorithm to solve the independent-set problem when each vertex in

G has degree 2. Analyze the running time, and prove that your algorithm works correctly.

d. Give an efficient algorithm to solve the independent-set problem when G is bipartite. Analyze the running time, and prove that your algorithm works correctly. (Hint: Use the results of Section 26.3.)

Answers

Maurice Tutor
(5)
Status NEW Posted 17 Sep 2017 09:09 AM My Price 5.00

Hel-----------lo -----------Sir-----------/Ma-----------dam-----------Tha-----------nk -----------You----------- fo-----------r u-----------sin-----------g o-----------ur -----------web-----------sit-----------e a-----------nd -----------and----------- ac-----------qui-----------sit-----------ion----------- of----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n.P-----------lea-----------se -----------pin-----------g m-----------e o-----------n c-----------hat----------- I -----------am -----------onl-----------ine----------- or----------- in-----------box----------- me----------- a -----------mes-----------sag-----------e I----------- wi-----------ll

Not Rated(0)