Minimum cost source location problem with vertex-connectivity requirements in digraphs

Given a digraph (or an undirected graph) G=(V,E) with a set V of vertices v with nonnegative real costs w(v), and a set E of edges and a positive integer k, we deal with the problem of finding a minimum cost subset SV such that, for each vertex vV−S, there are k vertex-disjoint paths from S to v. In this paper, we show that the problem can be solved by a greedy algorithm in time in a digraph (or in time in an undirected graph), where n=|V| and m=|E|. Based on this, given a digraph and two integers k and ℓ, we also give a polynomial time algorithm for finding a minimum cost subset SV such that for each vertex vV−S, there are k vertex-disjoint paths from S to v as well as ℓ vertex-disjoint paths from v to S.     

Markov models for digraph panel data: Monte Carlo-based derivative estimation

A parametric, continuous-time Markov model for digraph panel data is considered. The parameter is estimated by the method of moments. A convenient method for estimating the variance-covariance matrix of the moment estimator relies on the delta method, requiring the Jacobian matrix—that is, the matrix of partial derivatives—of the estimating function. The Jacobian matrix was estimated hitherto by Monte Carlo methods based on finite differences. Three new Monte Carlo estimators of the Jacobian matrix are proposed, which are related to the likelihood ratio/score function method of derivative estimation and have theoretical and practical advantages compared to the finite differences method. Some light is shed on the practical performance of the methods by applying them in a situation where the true Jacobian matrix is known and in a situation where the true Jacobian matrix is unknown.     

Hybrid Petri net and digraph approach for deadlock prevention in automated manufacturing systems

This paper proposes a hybrid approach to deadlock prevention in automated manufacturing systems that combines Petri nets (PNs) and digraphs, so taking advantage of the strong points of both techniques. The approach uses digraphs to make the detection of deadlock conditions easier and then translates the obtained information in empty siphons of the PN modelling the same system. The proposed methodology allows the implementation of new PN‐based deadlock prevention control policies. A case study and the simulation results show the benefits of the new control strategies.     

Some mathematical properties of cayley digraphs with applications to interconnection network design

We consider the relationships between Cayley digraphs and their coset graphs with respect to subgroups and obtain some general results on homomorphism and broadcasting between them. We also derive a general factorization theorem on subgraphs of Cayley digraphs by their automorphism groups. We discuss the applications of these results to well-known interconnection networks such as the butterfly network, the de Bruijn network, the cube-connected cycles network and the shuffle-exchange network.     

Integrated system fault diagnostics utilising digraph and fault tree-based approaches

With the growing intolerance to failures within systems, the issue of fault diagnosis has become ever prevalent. Information concerning these possible failures can help to minimise the disruption to the functionality of the system by allowing quick rectification. Traditional approaches to fault diagnosis within engineering systems have focused on sequential testing procedures and real-time mechanisms. Both methods have been predominantly limited to single fault causes. Latest approaches also consider the issue of multiple faults in reflection to the characteristics of modern day systems designed for high reliability. In addition, a diagnostic capability is required in real time and for changeable system functionality. This paper focuses on two approaches which have been developed to cater for the demands of diagnosis within current engineering systems, namely application of the fault tree analysis technique and the method of digraphs. Both use a comparative approach to consider differences between actual system behaviour and that expected. The procedural guidelines are discussed for each method, with an experimental aircraft fuel system used to test and demonstrate the features of the techniques. The effectiveness of the approaches is compared and their future potential highlighted.     

一种基于有向图的访问控制方法的研究

提出了一种基于有向图结构的数据关系的表示方法.这种方法直观地将数据之间的包含、信任关系表达出来,可以很方便地计算出对于某个特定的数据访问者所能访问的数据的集合和具体的访问权限,从而达到表达访问控制逻辑的目的.通过这种方法,可以把访问控制逻辑从应用层下降到数据管理层,大大简化应用系统的逻辑复杂度.