Priyadarsini P. L. K and Hemalatha T.
Connected Vertex Cover in 2Connected Planar Graph with Maximum Degree 4 is NPcomplete
570 - 573
2007
1
11
International Journal of Mathematical and Computational Sciences
https://publications.waset.org/pdf/13006
https://publications.waset.org/vol/11
World Academy of Science, Engineering and Technology
This paper proves that the problem of finding connected
vertex cover in a 2connected planar graph ( CVC2 ) with maximum degree 4 is NPcomplete. The motivation for proving this result is to
give a shorter and simpler proof of NPCompleteness of TRAMLC (the Top Right Access point MinimumLength Corridor) problem 1, by finding the reduction from CVC2. TRAMLC has many applications in laying optical fibre cables for data communication and electrical wiring in floor plans.The problem of finding connected vertex cover in any planar graph ( CVC ) with maximum degree 4 is NPcomplete 2. We first show that CVC2 belongs to NP and then we find a polynomial reduction from CVC to CVC2. Let a graph G0 and an integer K form an instance of CVC, where G0 is a planar graph and K is an upper bound on the size of the connected vertex cover in G0. We construct a 2connected planar graph, say G, by identifying the blocks and cut vertices of G0, and then finding the planar representation of all the blocks of G0, leading to a plane graph G1. We replace the cut vertices with cycles in such a way that the resultant graph G is a 2connected planar graph with maximum
degree 4. We consider L K 2t3 t i1 di where t is the number of cut vertices in G1 and di is the number of blocks for which ith cut vertex is common. We prove that G will have a connected vertex
cover with size less than or equal to L if and only if G0 has a connected vertex cover of size less than or equal to K.
Open Science Index 11, 2007