Vector Sorting
- PDF / 127,906 Bytes
- 1 Pages / 547.087 x 737.008 pts Page_size
- 49 Downloads / 170 Views
V
V
Valid-Utility Games Market Games and Content Distribution
VCG Generalized Vickrey Auction
Vector Sorting String Sorting
Vertex Coloring Distributed Vertex Coloring Exact Graph Coloring Using Inclusion–Exclusion
Vertex Cover Data Reduction Vertex Cover Kernelization
Vertex Cover Kernelization 2004; Abu-Khzam, Collins, Fellows, Langston, Suters, Symons JIANER CHEN Department of Computer Science, Texas A&M University, College Station, TX, USA
Problem Definition Let G be an undirected graph. A subset C of vertices in G is a vertex cover for G if every edge in G has at least one end in C. The (parametrized) VERTEX COVER problem is for each given instance (G, k), where G is a graph and k 0 is an integer (the parameter), to determine whether the graph G has a vertex cover of at most k vertices. The VERTEX COVER problem is one of the six “basic” NP-complete problems according to Garey and Johnson [4]. Therefore, the problem cannot be solved in polynomial time unless P = NP. However, the NPcompleteness of the problem does not obviate the need for solving it because of its fundamental importance and wide applications. One approach was initiated based on the observation that in many applications, the parameter k is small. Therefore, by taking the advantages of this fact, one may be able to solve this NP-complete problem effectively and practically for instances with a small parameter. More specifically, algorithms of running time of the form f (k)p(n) have been studied for VERTEX COVER, where p(n) is a low-degree polynomial of the number n = jGj of vertices in G and f (k) is a function independent of n. There has been an impressive sequence of improved algorithms for the VERTEX COVER problem. A number of new techniques have been developed during this research, including kernelization, folding, and refined branch-andsearch. In particular, the kernelization method is the study of polynomial time algorithms that can significantly reduce the instance size for VERTEX COVER. The following are some concepts related to the kernelization method: Definition 1 Two instances (G, k) and (G 0 ; k 0 ) of VERTEX COVER are equivalent if the graph G has a vertex cover of size k if and only if the graph G0 has a vertex cover of size k 0 . A kernelization algorithm for the VERproblem takes an instance (G, k) of VERTEX COVER as input and produces an equivalent instance (G 0 ; k 0 ) for the problem, such that jG 0 j jGj and k 0 k.
Definition 2 Keywords and Synonyms Vertex cover preprocessing; Vertex cover data reduction
TEX COVER
1003
Data Loading...
