KBSE60

Theorem. PLANAR-3-COLORABILITY ≣ P PLANAR-MAP-3-COLORABILITY.(A plane three-coloring problem can be mutually regulated with a plane graph three-coloring problem!) Proof 2.Planar 3-colorability is NP-completeprove:a. First prove that it is an NP problem. It is a good proof as long as we find one of the solutions in polynomial time.b. We can reduce the 3-colorability problem to the flat 3-colorability problem.c. Given any 3 coloring instance G, … Continue reading KBSE60

KBSE42

The Hitting Set Problem is actually NP-complete Problem Description:Given a set {S1, S2, S3,…, Sn} and budget b, find a set H, where H intersects all Si and the size of H does not exceed b. Prove that the problem is NP-complete (1) Prove that the problem is an NP problem.Assuming that all elements of the set H are given, it is obviously possible to … Continue reading KBSE42

KBSE30

Merge Sort Analysis of AlgorithmsMerge sorting is an effective sorting algorithm based on merge operations. This algorithm is a very typical application using the divide and conquer method (Divide and Conquer). Combine existing ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence in order, and then make the subsequences in order. If two ordered lists are merged into one ordered … Continue reading KBSE30