Parameterized computation is a new method dealing with NP-hard problems, which has attracted a lot of attentions in theoretical computer science. As a practical preprocessing method for NP-hard problems, kernelizaiton...Parameterized computation is a new method dealing with NP-hard problems, which has attracted a lot of attentions in theoretical computer science. As a practical preprocessing method for NP-hard problems, kernelizaiton in parameterized computation has recently become an active research area. In this paper, we discuss several kernelizaiton techniques, such as crown decomposition, planar graph vertex partition, randomized methods, and kernel lower bounds, which have been used widely in the kernelization of many hard problems.展开更多
The presence of Dirac delta function in differential equation can lead to a discontinuity,which may degrade the accuracy of related numerical methods.To improve the accuracy,a secondorder numerical method for elliptic...The presence of Dirac delta function in differential equation can lead to a discontinuity,which may degrade the accuracy of related numerical methods.To improve the accuracy,a secondorder numerical method for elliptic equations with singular sources is introduced by employing a local kernel flter.In this method,the discontinuous equation is convoluted with the kernel function to obtain a more regular one.Then the original equation is replaced by this fltered equation around the singular points,to obtain discrete numerical form.The unchanged equations at the other points are discretized by using a central difference scheme.1D and 2D examples are carried out to validate the correctness and accuracy of the present method.The results show that a second-order of accuracy can be obtained in the fltering framework with an appropriate integration rule.Furthermore,the present method does not need any jump condition,and also has extremely simple form that can be easily extended to high dimensional cases and complex geometry.展开更多
基金supported by the National Natural Science Foundation of China (Nos. 61173051, 61103033, and 61232001)
文摘Parameterized computation is a new method dealing with NP-hard problems, which has attracted a lot of attentions in theoretical computer science. As a practical preprocessing method for NP-hard problems, kernelizaiton in parameterized computation has recently become an active research area. In this paper, we discuss several kernelizaiton techniques, such as crown decomposition, planar graph vertex partition, randomized methods, and kernel lower bounds, which have been used widely in the kernelization of many hard problems.
基金supported by the National Natural Science Foundation in China(Grant Nos.51076006,11202013)BUAA SJP ‘‘111’’ Program(Grant No.B08009)+1 种基金the National Basic Research Program of China(2012CB720200)the Open Research Fund of MOE Key Lab-oratory of High-speed Railway Engineering,Southwest Jiao-tong University and the European Community’s Seventh Framework Program(FP7/2007-2013)under Grant agreement 225967‘‘NextMuSE’’
文摘The presence of Dirac delta function in differential equation can lead to a discontinuity,which may degrade the accuracy of related numerical methods.To improve the accuracy,a secondorder numerical method for elliptic equations with singular sources is introduced by employing a local kernel flter.In this method,the discontinuous equation is convoluted with the kernel function to obtain a more regular one.Then the original equation is replaced by this fltered equation around the singular points,to obtain discrete numerical form.The unchanged equations at the other points are discretized by using a central difference scheme.1D and 2D examples are carried out to validate the correctness and accuracy of the present method.The results show that a second-order of accuracy can be obtained in the fltering framework with an appropriate integration rule.Furthermore,the present method does not need any jump condition,and also has extremely simple form that can be easily extended to high dimensional cases and complex geometry.
