TADM2E 9.17

From Algorithm Wiki
Revision as of 18:24, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Take an instance of vertex cover VC(G,k)

Create G': for each edge create {u, v} create a new vertex uv. create edges {u, uv} and {v, uv}

Call Dom-SET(G',k)