翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク kernelization ： ウィキペディア英語版 kernelization In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to the desired output for the original problem. Kernelization is often achieved by applying a set of reduction rules that cut away parts of the instance that are easy to handle. In parameterized complexity theory, it is often possible to prove that a kernel with guaranteed bounds on the size of a kernel (as a function of some parameter associated to the problem) can be found in polynomial time. When this is possible, it results in a fixed-parameter tractable algorithm whose running time is the sum of the (polynomial time) kernelization step and the (non-polynomial but bounded by the parameter) time to solve the kernel. Indeed, every problem that can be solved by a fixed-parameter tractable algorithm can be solved by a kernelization algorithm of this type. ==Example: vertex cover== A standard example for a kernelization algorithm is the kernelization of the vertex cover problem by S. Buss.〔This unpublished observation is acknowledged in a paper of 〕 In this problem, the input is an undirected graph $G$ together with a number $k$. The output is a set of at most $k$ vertices that includes the endpoint of every edge in the graph, if such a set exists, or a failure exception if no such set exists. This problem is NP-hard. However, the following reduction rules may be used to kernelize it: # If $k>0$ and $v$ is a vertex of degree greater than $k$, remove $v$ from the graph and decrease $k$ by one. Every vertex cover of size $k$ must contain $v$ since otherwise too many of its neighbors would have to be picked to cover the incident edges. Thus, an optimal vertex cover for the original graph may be formed from a cover of the reduced problem by adding $v$ back to the cover. # If $v$ is an isolated vertex, remove it. An isolated vertex cannot cover any edges, so in this case $v$ cannot be part of any minimal cover. # If more than $k^2$ edges remain in the graph, and neither of the previous two rules can be applied, then the graph cannot contain a vertex cover of size $k$. For, after eliminating all vertices of degree greater than $k$, each remaining vertex can only cover at most $k$ edges and a set of $k$ vertices could only cover at most $k^2$ edges. In this case, the instance may be replaced by an instance with two vertices, one edge, and $k=0$ , which also has no solution. An algorithm that applies these rules repeatedly until no more reductions can be made necessarily terminates with a kernel that has at most $k^2$ edges and (because each edge has at most two endpoints and there are no isolated vertices) at most $2k^2$ vertices. This kernelization may be implemented in linear time. Once the kernel has been constructed, the vertex cover problem may be solved by a brute force search algorithm that tests whether each subset of the kernel is a cover of the kernel. Thus, the vertex cover problem can be solved in time $O(2^+n+m)$ for a graph with $n$ vertices and $m$ edges, allowing it to be solved efficiently when $k$ is small even if $n$ and $m$ are both large. Although this bound is fixed-parameter tractable, its dependence on the parameter is higher than might be desired. More complex kernelization procedures can improve this bound, by finding smaller kernels, at the expense of greater running time in the kernelization step. In the vertex cover example, kernelization algorithms are known that produce kernels with at most $2k$ vertices. One algorithm that achieves this improved bound exploits the half-integrality of the linear program relaxation of vertex cover due to Nemhauser and Trotter. Another kernelization algorithm achieving that bound is based on what is known as the crown reduction rule and uses alternating path arguments.〔 give a kernel based on the crown reduction that has $3k$ vertices. The $2k$ vertex bound is a bit more involved and folklore.〕 The currently best known kernelization algorithm in terms of the number of vertices is due to and achieves $2k-c\backslash log\; k$ vertices for any fixed constant $c$. It is not possible, in this problem, to find a kernel of size $O(\backslash log\; k)$, unless P = NP, for such a kernel would lead to a polynomial-time algorithm for the NP-hard vertex cover problem. However, much stronger bounds on the kernel size can be proven in this case: unless coNP $\backslash subseteq$ NP/poly (believed unlikely by complexity theorists), for every $\backslash epsilon>0$ it is impossible in polynomial time to find kernels with $O(k^)$ edges. It is unknown for vertex cover whether kernels with $(2-\backslash epsilon)k$ vertices for some $\backslash epsilon>0$ would have any unlikely complexity-theoretic consequences. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「kernelization」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.