This paper believes that complex feedback systems are very common and important in the modern engineering technology. It is very difficult to resolve the optimum problem of the complex feedback system. But it has impo...This paper believes that complex feedback systems are very common and important in the modern engineering technology. It is very difficult to resolve the optimum problem of the complex feedback system. But it has important practical value. This paper decomposed the complex feedback system into many subsystems by means of the decomposing method. First, optimize each subsystem on the optimization basis. Second optimize the whole system step by step. Finally, we provide an example of the optimal design of the heat-exchanger used in chemical processes.展开更多
This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the p...This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the problem has been the subject of intensive study. Motivated by the parameter ecology program we attempt to classify the parameterized and kernelization complexity of FEEDBACK VERTEX SET for a wide range of parameters.We survey known results and present several new complexity classifications. For example, we prove that FEEDBACK VERTEX SET is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph. We also prove that the problem admits a polynomial kernel when parameterized by the vertex-deletion distance to a pseudo forest, a graph in which every connected component has at most one cycle. In contrast, we prove that a slightly smaller parameterization does not allow for a polynomial kernel unless NP coNP=poly and the polynomial-time hierarchy collapses.展开更多
We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice ...We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.展开更多
文摘This paper believes that complex feedback systems are very common and important in the modern engineering technology. It is very difficult to resolve the optimum problem of the complex feedback system. But it has important practical value. This paper decomposed the complex feedback system into many subsystems by means of the decomposing method. First, optimize each subsystem on the optimization basis. Second optimize the whole system step by step. Finally, we provide an example of the optimal design of the heat-exchanger used in chemical processes.
基金supported by the European Research Council through Starting Grant 306992 "Parameterized Approximation"
文摘This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the problem has been the subject of intensive study. Motivated by the parameter ecology program we attempt to classify the parameterized and kernelization complexity of FEEDBACK VERTEX SET for a wide range of parameters.We survey known results and present several new complexity classifications. For example, we prove that FEEDBACK VERTEX SET is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph. We also prove that the problem admits a polynomial kernel when parameterized by the vertex-deletion distance to a pseudo forest, a graph in which every connected component has at most one cycle. In contrast, we prove that a slightly smaller parameterization does not allow for a polynomial kernel unless NP coNP=poly and the polynomial-time hierarchy collapses.
基金supported by a GermanNorwegian PPP grantsupported by the Indo-German Max Planck Center for Computer Science (IMPECS)
文摘We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.
