An independent set in a graph g

Assignment Help Data Structure & Algorithms

Reference no: EM13161039

An independent set in a graph G is a set of vertices I in G such that no two vertices in I are adjacent (neighbors). The maximum independent set problem is, given a graph G, to compute an independent set of maximum size (maximum number of vertices) in G. Pinocchio claims that he has a greedy algorithm that solves the maximum independent set problem. Pinocchio's algorithm works as follows. The algorithm initializes the set I to the empty set, and repeats the following steps: Pick a vertex in the graph with the minimum degree, add it to the set I, and remove it and all the vertices adjacent to it from the graph. The algorithm stops when the graph is empty. Does Pinocchio's greedy algorithm always produces a maximum independent set? Prove your answer (if it does, give a proof; if it does not, give a counter example,that is, a graph on which Pinocchio's algorithm does not produce a
maximum independent set).

Reference no: EM13161039

Questions Cloud

Design a performance appraisal record for use : Design a performance appraisal record for use in a performance appraisal interview and write a job advertisement for the position.

Compare and contrast photosynthesis and respiration : Compare and contrast photosynthesis and respiration, with respect to their detailed mechanisms and their outcomes. Mention the key kinds ofmolecules that participate in both processes.

Hybridized carbon would form the most stable carbocation : This electrophilic addition reaction involves a carbocation intermediate. Protonation of which sp2 hybridized carbon would form the most stable carbocation?

Malicious attacks and / or threats that you identified : For each of the three (3) or more malicious attacks and / or threats that you identified in Assignment 1, choose a strategy for addressing the associated risk (i.e., risk mitigation, risk assignment, risk acceptance, or risk avoidance). Explain your ..

An independent set in a graph g : An independent set in a graph G is a set of vertices I in G such that no two vertices in I are adjacent (neighbors). The maximum independent set problem is, given a graph G, to compute an independent set of maximum size (maximum number of vertices) i..

Describe the molecular events that cause the shortening : Tell what telomeres are and why are they important individing cells. What is the worst case scenario for telomere lossin rapidly dividing cells?

State what is the empirical formula of a compound composed : What is the empirical formula of a compound composed of 3.25% hydrogen (H), 19.36% carbon (C), and 77.39% oxygen (O) by mass? 2. A compound with the empirical formula CH2 has a molar mass of 84 g/mol. What is the molecular formula for this compoun..

You have 10 stacks of coins : You have 10 stacks of coins, each consisting of 10 quarters. One entire stack is counterfeit, but you do not know which one. You do know the weight of a genuine quarter and you are also told that each counterfeit quarter weights one gram more than it..

Compare the effect of a triple frameshift minus : Imagine a gene that codes for a protein of 1000 amino acids.Compare the effect of a triple frameshift minus mutation thatoccurs at +19, +22 and +24 bp and one that occurs at +30, +1500,and +2900 bp.

User Account

All Pages