This study investigates the robust feedback set stabilization of switched logic control networks(SLCNs)with state-dependent uncertain switching and control constraints.First,based on the properties of the semi-tensor ...This study investigates the robust feedback set stabilization of switched logic control networks(SLCNs)with state-dependent uncertain switching and control constraints.First,based on the properties of the semi-tensor product of matrices and the vector representation of logic,an SLCN with state-dependent uncertain switching and control constraints is expressed in algebraic form.Second,an input transformation and a switching model are constructed to transfer the original SLCN into one with a free control input and arbitrary switching.The equivalence between the set stabilizability of the original SLCN and that of the resulting SLCN is established.Based on such equivalence,the authors propose a necessary and sufficient condition for robust feedback set stabilizability.Finally,an example is presented to demonstrate the application of the results obtained.展开更多
A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vert...A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.展开更多
The movement of a particle could be depicted by the Mandelbrot set from the fractal viewpoint. According to the requirement, the movement of the particle needs to show different behaviors. In this paper, the feedback ...The movement of a particle could be depicted by the Mandelbrot set from the fractal viewpoint. According to the requirement, the movement of the particle needs to show different behaviors. In this paper, the feedback control method is taken on the classical Mandelbrot set. By amending the feedback item in the controller, the control method is applied to the generalized Mandelbrot set and by taking the reference item to be the trajectory of another system, the synchronization of Mandelbrot sets is achieved.展开更多
The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit desi...The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit design, synchronous systems, computer systems, and very-large-scale integration (VLSI) circuits. The FVS problem is known to be NP-hard for simple graphs, but polynomi-al-time algorithms have been found for special classes of graphs. The intersection graph of a collection of arcs on a circle is called a circular-arc graph. A normal Helly circular-arc graph is a proper subclass of the set of circular-arc graphs. In this paper, we present an algorithm that takes time to solve the FVS problem in a normal Helly circular-arc graph with n vertices and m edges.展开更多
Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex s...Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition.展开更多
反馈集问题(feedback set problem)是计算机科学中研究最为广泛和深入的图上NP完全问题之一,其在并发计算、大规模集成电路、编码设计、软件验证、社交网络分析等领域均存在重要的应用.子集反馈集问题(subset feedback set problem)是...反馈集问题(feedback set problem)是计算机科学中研究最为广泛和深入的图上NP完全问题之一,其在并发计算、大规模集成电路、编码设计、软件验证、社交网络分析等领域均存在重要的应用.子集反馈集问题(subset feedback set problem)是反馈集问题的一种更一般化的形式,更加具有普适性和实用性.近年来,这2个问题在计算复杂性上的分类工作已逐步完善,在算法领域也已出现许多重要的突破.相关研究工作分为2个部分进行介绍.第1部分详尽地介绍了反馈集和子集反馈集各种不同版本的问题,梳理了它们之间的一些重要关系,并介绍了这些问题在一般图上的计算复杂性.第2部分系统性地介绍了反馈集和子集反馈集问题在一些重要子图类上的计算复杂性,包括度有界的图类、平面图类、竞赛图图类、相交图类、禁止图图类和二部图图类.最后对反馈集和子集反馈集问题的研究现状进行分析和总结,概括了目前主流的研究趋势.展开更多
A feedback vertex set in a graph G\S is a vertex subset S such that is acyclic.The girth of a graph is the minimum cycle length in G.In this paper,some results are proven:(i)Every connected graph G has a feedback vert...A feedback vertex set in a graph G\S is a vertex subset S such that is acyclic.The girth of a graph is the minimum cycle length in G.In this paper,some results are proven:(i)Every connected graph G has a feedback vertex set at most m/3 and the bound is tight if and only if G is K_(3)orK_(4).(ii)Alon et al.(J Graph Theory 38:113–123,2001)proved every connected triangle-free graph G has a feedback vertex set at most m/4.We prove the bound is tight if and only if G is 4-cycle,Square-Claw or Double-Squares.(iii)Every connected outerplanar graph G with girth k has a feedback vertex set at most m/k and the bound is tight if and only if G is a k-cycle.This result verifies the conjecture of Dross et al.(Discrete Appl Math 214:99–107,2016)on outerplanar graph.展开更多
基金supported by the National Natural Science Foundation of China under Grant Nos.61873284,61321003,and 62373374.
文摘This study investigates the robust feedback set stabilization of switched logic control networks(SLCNs)with state-dependent uncertain switching and control constraints.First,based on the properties of the semi-tensor product of matrices and the vector representation of logic,an SLCN with state-dependent uncertain switching and control constraints is expressed in algebraic form.Second,an input transformation and a switching model are constructed to transfer the original SLCN into one with a free control input and arbitrary switching.The equivalence between the set stabilizability of the original SLCN and that of the resulting SLCN is established.Based on such equivalence,the authors propose a necessary and sufficient condition for robust feedback set stabilizability.Finally,an example is presented to demonstrate the application of the results obtained.
文摘A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.
基金Project supported by the National Natural Science Foundation of China (Grant No. 10971120)the Natural Science Foundation of Shandong Province, China(Grant Nos. ZR2010FM010 and ZR2011FQ035)the Independent Innovation Foundation of Shandong University, China (Grant No. 2011ZRYQ012)
文摘The movement of a particle could be depicted by the Mandelbrot set from the fractal viewpoint. According to the requirement, the movement of the particle needs to show different behaviors. In this paper, the feedback control method is taken on the classical Mandelbrot set. By amending the feedback item in the controller, the control method is applied to the generalized Mandelbrot set and by taking the reference item to be the trajectory of another system, the synchronization of Mandelbrot sets is achieved.
文摘The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit design, synchronous systems, computer systems, and very-large-scale integration (VLSI) circuits. The FVS problem is known to be NP-hard for simple graphs, but polynomi-al-time algorithms have been found for special classes of graphs. The intersection graph of a collection of arcs on a circle is called a circular-arc graph. A normal Helly circular-arc graph is a proper subclass of the set of circular-arc graphs. In this paper, we present an algorithm that takes time to solve the FVS problem in a normal Helly circular-arc graph with n vertices and m edges.
基金Partially supported by the National Natural Science Foundation of China( 1 0 2 71 0 65
文摘Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition.
文摘反馈集问题(feedback set problem)是计算机科学中研究最为广泛和深入的图上NP完全问题之一,其在并发计算、大规模集成电路、编码设计、软件验证、社交网络分析等领域均存在重要的应用.子集反馈集问题(subset feedback set problem)是反馈集问题的一种更一般化的形式,更加具有普适性和实用性.近年来,这2个问题在计算复杂性上的分类工作已逐步完善,在算法领域也已出现许多重要的突破.相关研究工作分为2个部分进行介绍.第1部分详尽地介绍了反馈集和子集反馈集各种不同版本的问题,梳理了它们之间的一些重要关系,并介绍了这些问题在一般图上的计算复杂性.第2部分系统性地介绍了反馈集和子集反馈集问题在一些重要子图类上的计算复杂性,包括度有界的图类、平面图类、竞赛图图类、相交图类、禁止图图类和二部图图类.最后对反馈集和子集反馈集问题的研究现状进行分析和总结,概括了目前主流的研究趋势.
基金supported by the National Natural Science Foundation of China(Nos.11901605,12101069)the disciplinary funding of Central University of Finance and Economics,the Emerging Interdisciplinary Project of CUFE.
文摘A feedback vertex set in a graph G\S is a vertex subset S such that is acyclic.The girth of a graph is the minimum cycle length in G.In this paper,some results are proven:(i)Every connected graph G has a feedback vertex set at most m/3 and the bound is tight if and only if G is K_(3)orK_(4).(ii)Alon et al.(J Graph Theory 38:113–123,2001)proved every connected triangle-free graph G has a feedback vertex set at most m/4.We prove the bound is tight if and only if G is 4-cycle,Square-Claw or Double-Squares.(iii)Every connected outerplanar graph G with girth k has a feedback vertex set at most m/k and the bound is tight if and only if G is a k-cycle.This result verifies the conjecture of Dross et al.(Discrete Appl Math 214:99–107,2016)on outerplanar graph.
