Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).     

Ehrenfeucht-Fraïssé games in finite set theory

In this article, with Ehrenfeucht-Fraïssé games we prove that Δ₁≠Δ₀ on BFR, which implies Δ≠Δ₀ on BFR, and thus solve an open problem raised by Albert Atserias in his dissertation (Δ₀,Δ₁,Δ are fragments of first order logic and BFR is a class of finite sets which in essence is equivalent to a class of finite pure arithmetic structures with built-in BIT predicate).     

Static Bayesian games with finite fuzzy types and the existence of equilibrium

This paper studies a special game with incomplete information, in which the payoffs of the players are both random and fuzzy. Such a game is considered in the context of a Bayesian game with the uncertain types characterized as fuzzy variables. A static fuzzy Bayesian game is then introduced and the decision rules for players are given based on credibility theory. We further prove the existence of the equilibrium of the game. Finally, a Cournot competition model with fuzzy efficiency under asymmetric information is investigated as an application and some results are presented.     

Fault tolerance in cellular automata at high fault rates

A commonly used model for fault-tolerant computation is that of cellular automata. The essential difficulty of fault-tolerant computation is present in the special case of simply remembering a bit in the presence of faults, and that is the case we treat in this paper. We are concerned with the degree (the number of neighboring cells on which the state transition function depends) needed to achieve fault tolerance when the fault rate is high (nearly 1/2). We consider both the traditional transient fault model (where faults occur independently in time and space) and a recently introduced combined fault model which also includes manufacturing faults (which occur independently in space, but which affect cells for all time). We also consider both a purely probabilistic fault model (in which the states of cells are perturbed at exactly the fault rate) and an adversarial model (in which the occurrence of a fault gives control of the state to an omniscient adversary). We show that there are cellular automata that can tolerate a fault rate 1/2−ξ (with ξ>0) with degree O((1/ξ²)log(1/ξ)), even with adversarial combined faults. The simplest such automata are based on infinite regular trees, but our results also apply to other structures (such as hyperbolic tessellations) that contain infinite regular trees. We also obtain a lower bound of Ω(1/ξ²), even with only purely probabilistic transient faults.     

Path Hitting in Acyclic Graphs

An instance of the path hitting problem consists of two families of paths, and ℋ, in a common undirected graph, where each path in ℋ is associated with a non-negative cost. We refer to and ℋ as the sets of demand and hitting paths, respectively. When p∈ℋ and share at least one mutual edge, we say that p hits q. The objective is to find a minimum cost subset of ℋ whose members collectively hit those of . In this paper we provide constant factor approximation algorithms for path hitting, confined to instances in which the underlying graph is a tree, a spider, or a star. Although such restricted settings may appear to be very simple, we demonstrate that they still capture some of the most basic covering problems in graphs. Our approach combines several novel ideas: We extend the algorithm of Garg, Vazirani and Yannakakis (Algorithmica, 18:3–20, 1997) for approximate multicuts and multicommodity flows in trees to prove new integrality properties; we present a reduction that involves multiple calls to this extended algorithm; and we introduce a polynomial-time solvable variant of the edge cover problem, which may be of independent interest. An extended abstract of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms, 2006. This work is part of D. Segev’s Ph.D. thesis prepared at Tel-Aviv University under the supervision of Prof. Refael Hassin.     

一类不确定Lur'e奇异系统的可靠鲁棒H_∞跟踪控制(英文)

The problem of reliable robust H_∞tracking control for a class of uncertain Lur'e singular systems is studied.A practical and general failure model of actuator and sensor is considered by using convex polytopic uncertainties to describe control surface impairment.Some sufficient conditions are presented for the case of actuator,sensor and control surface failures in terms of linear matrix inequalities (LMIs).The resultant control systems are reliable in that they guarantee closed-loop system robust stability with H_∞performance and the output tracking the reference signal without steady-state error when all control components are operational as well as when some control components experience failures.Finally,a numerical example is given to show the effectiveness of the proposed methods.     

Global dynamics for non-autonomous reaction-diffusion neural networks with time-varying delays

In this paper, a class of non-autonomous reaction-diffusion neural networks with time-varying delays is considered. Novel methods to study the global dynamical behavior of these systems are proposed. Employing the properties of diffusion operator and the method of delayed inequalities analysis, we investigate global exponential stability, positive invariant sets and global attracting sets of the neural networks under consideration. Furthermore, conditions sufficient for the existence and uniqueness of periodic attractors for periodic neural networks are derived and the existence range of the attractors is estimated. Finally two examples are given to demonstrate the effectiveness of these results.     

Approximation algorithms for partially covering with edges

The edge dominating set (EDS) and edge-cover (EC) problems are classical graph covering problems in which one seeks a minimum cost collection of edges which covers the edges or vertices, respectively, of a graph. We consider the generalized partial cover version of these problems, in which failing to cover an edge, in the EDS case, or vertex, in the EC case, induces a penalty. Given a bound on the total amount of penalties that we are permitted to pay, the objective is to find a minimum cost cover with respect to this bound. We give an 8/3-approximation for generalized partial EDS. This result matches the best-known guarantee for the {0,1}-EDS problem, a specialization in which only a specified set of edges need to be covered. Moreover, 8/3 corresponds to the integrality gap of the natural formulation of the {0,1}-EDS problem. Our techniques can also be used to derive an approximation scheme for the generalized partial edge-cover problem, which is -complete even though the uniform penalty version of the partial edge-cover problem is in .