Convergence analysis of directed signed networks via an M-matrix approach

This paper aims at solving convergence problems on directed signed networks with multiple nodes, where interactions among nodes are described by signed digraphs. The convergence analysis is achieved by matrix-theoretic and graph-theoretic tools, in which M-matrices play a central role. The fundamental digon sign-symmetry assumption upon signed digraphs can be removed with the proposed analysis approach. Furthermore, necessary and sufficient conditions are established for semi-positive and positive stabilities of Laplacian matrices of signed digraphs, respectively. A benefit of this result is that given strong connectivity, a directed signed network can achieve bipartite consensus (or state stability) if and only if the signed digraph associated with it is structurally balanced (or unbalanced). If the interactions between nodes are described by a signed digraph only with spanning trees, a directed signed network can achieve interval bipartite consensus (or state stability) if and only if the signed digraph contains a structurally balanced (or unbalanced) rooted subgraph. Simulations are given to illustrate the developed results by considering signed networks associated with digon sign-unsymmetric signed digraphs.     

Estimation of digraph costs for keyboard layout optimization

The main aim of this study was to estimate the digraph costs (interkey-stroke times) based on the digraph (two consecutive keys) tapping rates for the optimization of keyboard layouts considering the touch typing principles. The study also investigated the effects of column, row, hand and period on digraph-tapping rate. For the purpose, a laboratory experiment was performed with seven subjects using a conventional keyboard. Digraph-tapping rates of a total of 241 same hand digraphs were recorded for a duration of 2-min. The interkey-stroke times were calculated as the digraph costs for the same hand digraphs using the estimated mean digraph-tapping rates. The different hand digraph costs were calculated based on the same hand digraph costs and the results of a previous study. The results indicated significant column, row, hand and period effect on the digraph-tapping rate. Using the digraph costs and the digraph frequencies of the considered language in a quadratic assignment problem, an optimal touch typing keyboard layout can be developed to satisfy all but one of Dvorak's touch typing criteria. As an application, an optimal keyboard layout, called Turkish I-layout, is developed for Turkish language. The comparison results between I and existing Turkish F and Q layouts showed that the I-layout is superior both according to the results of the optimization and Dvorak's criteria.Relevance to industryOptimal and ergonomic keyboard layouts improve typing performance and reduce the likelihood of upper extremity disorders. The digraph-tapping rates estimated through this study are essential for the development of such layouts.     

Multiple-attribute decision making methods for plant layout design problem

The layout design problem is a strategic issue and has a significant impact on the efficiency of a manufacturing system. Much of the existing layout design literature that uses a surrogate function for flow distance or for simplified objectives may be entrapped into local optimum; and subsequently lead to a poor layout design due to the multiple-attribute decision making (MADM) nature of a layout design decision. The present study explores the use of MADM approaches in solving a layout design problem. The proposed methodology is illustrated through a practical application from an IC packaging company. Two methods are proposed in solving the case study problem: Technique for order preference by similarity to ideal solution (TOPSIS) and fuzzy TOPSIS. Empirical results showed that the proposed methods are viable approaches in solving a layout design problem. TOPSIS is a viable approach for the case study problem and is suitable for precise value performance ratings. When the performance ratings are vague and imprecise, the fuzzy TOPSIS is a preferred solution method.     

Drawing directed graphs using quadratic programming

We describe a new method for visualization of directed graphs. The method combines constraint programming techniques with a high performance force-directed placement (FDP) algorithm. The resulting placements highlight hierarchy in directed graphs while retaining useful properties of FDP; such as emphasis of symmetries and preservation of proximity relations. Our algorithm automatically identifies those parts of the digraph that contain hierarchical information and draws them accordingly. Additionally, those parts that do not contain hierarchy are drawn at the same quality expected from a nonhierarchical, undirected layout algorithm. Our experiments show that this new approach is better able to convey the structure of large digraphs than the most widely used hierarchical graph-drawing method. An interesting application of our algorithm is directional multidimensional scaling (DMDS). DMDS deals with low-dimensional embedding of multivariate data where we want to emphasize the overall flow in the data (e.g., chronological progress) along one of the axes.     

Factorization of de Bruijn digraphs by cycle-rooted trees

In this paper, we introduce a new concept of an arc-coloring of digraphs called in-coloring. An in-coloring of an in-regular digraph induces a factorization into cycle-rooted trees; a cycle-rooted tree is a weakly connected digraph in which every vertex has indegree one. In particular, we study in-colorings of a line digraph. The results interpolate one-factorizations and tree factorizations of the de Bruijn digraph.     

Using graph parsing for automatic graph drawing

This paper presents a procedure for automatically drawing directed graphs. Our system, Clan-based Graph Drawing Tool (CG), uses a unique clan-based graph decomposition to determine intrinsic substructures (clans) in the graph and to produce a parse tree. The tree is given attributes that specify the node layout. CG then uses tree properties with the addition of “routing nodes” to route the edges. The objective of the system is to provide, automatically, an aesthetically pleasing visual layout for arbitrary directed graphs. The prototype has shown the strengths of this approach. The innovative strategy of clan-based graph decomposition is the first digraph drawing technique to analyze locality in the graph in two dimensions. The typical approach to drawing digraphs uses a single dimension, level, to arrange the nodes     

每条弧都在Hamilton-路上的半完全多部有向图

用一条弧或一对方向相反的弧代替完全多部无向图的每一条边所得到的有向图被称为是半完全多部有向图。2002年L. Volkmann [6]提出这样一个问题：给出半完全多部有向图中每一条弧都在Hamilton-路上的充分条件。本文将针对此问题给出一个新的充分条件,并举例说明该充分条件的独立性以及它在某种意义下的最佳可能性。     

Book Embeddability of Series–Parallel Digraphs

In this paper we deal with the problem of computing upward two-page book embeddings of Two Terminal Series-Parallel (TTSP) digraphs, which are a subclass of series-parallel digraphs. An optimal O(n) time and space algorithm to compute an upward two-page book embedding of a TTSP-digraph with n vertices is presented. A previous algorithm of Alzohairi and Rival [1] runs in O(n³) time and assumes that the input series-parallel digraph does not have transitive edges. An application of this result to a computational geometry problem is also discussed. More precisely, upward two-page book embeddings are used to deal with the upward point-set embeddability problem, i.e., the problem of mapping planar digraphs onto a given set of points in the plane so that all edges are monotonically increasing in a common direction. The equivalence between upward two-page book embeddability and upward point-set embeddability with at most one bend per edge on any given set of points is proved. An O(n log n)-time algorithm for computing an upward point-set embedding with at most one bend per edge for TTSP-digraphs is presented.     

Absorbant of generalized de Bruijn digraphs

The generalized de Bruijn digraph GB(n,d) has good properties as an interconnection network topology. The resource location problem in an interconnection network is one of the facility location problems. Finding absorbants of a digraph corresponds to solving a kind of resource location problem. In this paper, we establish bounds on the absorbant number for GB(n,d), and we give some sufficient conditions for the absorbant number of GB(n,d) to achieve the bounds. When d divides n, the extremal digraphs achieving the upper bound are characterized by determining their absorbants.     

有向图连通支配集求解算法

定义了有向图指定源点连通支配集问题。借助参数算法中的技术设计了针对该问题的规约规则,通过规约规则的实施来降低原问题的规模;随后又设计了近似算法在规约后的有向图中求出一个较小的连通支配集;最后结合规约规则带来的一些良好特性设计了优化规则,通过优化变换的实施进一步缩减由近似算法求得的连通支配集。不同模型随机图上的模拟实验表明这些规则和算法是有效的。     

On the feedback vertex set problem for a planar graph

An algorithm solving the feedback-vertex-set problem for planar digraphs is described. In particular, planar graphs with a certain additional condition are considered as they arise from solving systems of linear equations obtained from convection-dominated flow problems. The proposed algorithm requires a computational work linear in the size of the graph. Furthermore, a side-product is a decomposition of the graph into subsets that are of interest for block-Gauß-Seidel smoothers in multi-grid methods.     

Quasi-Upward Planarity

An upward planar drawing of a directed graph (digraph) is a planar drawing such that all the edges are represented by curves monotonically increasing in the vertical direction. In this paper we introduce and study the concept of quasi-upward planarity. Quasi-upward planarity allows us to extend the upward planarity theory to a large class of digraphs including digraphs that also have directed cycles. First, we characterize the digraphs that have a quasi-upward planar drawing. Second, we give a polynomial time algorithm for computing ``optimal'' quasi-upward planar drawings within a given planar embedding. Further, we apply branch and bound techniques to the problem of computing optimal quasi-upward planar drawings, considering all possible planar embeddings. The paper also contains experimental results about the proposed techniques.     

A new parallel algorithm for vertex priorities of data flow acyclic digraphs

Data flow acyclic directed graphs (digraph) are widely used to describe the data dependency of mesh-based scientific computing. The parallel execution of such digraphs can approximately depict the flowchart of parallel computing. During the period of parallel execution, vertex priorities are key performance factors. This paper firstly takes the distributed digraph and its resource-constrained parallel scheduling as the vertex priorities model, and then presents a new parallel algorithm for the solution of vertex priorities using the well-known technique of forward–backward iterations. Especially, in each iteration, a more efficient vertex ranking strategy is proposed. In the case of simple digraphs, both theoretical analysis and benchmarks show that the vertex priorities produced by such an algorithm will make the digraph scheduling time converge non-increasingly with the number of iterations. In other cases of non-simple digraphs, benchmarks also show that the new algorithm is superior to many traditional approaches. Embedding the new algorithm into the heuristic framework for the parallel sweeping solution of neutron transport applications, the new vertex priorities improve the performance by 20 % or so while the number of processors scales up from 32 to 2048.     

Quasi-Upward Planarity

Abstract. An upward planar drawing of a directed graph (digraph) is a planar drawing such that all the edges are represented by curves monotonically increasing in the vertical direction. In this paper we introduce and study the concept of quasi-upward planarity. Quasi-upward planarity allows us to extend the upward planarity theory to a large class of digraphs including digraphs that also have directed cycles. First, we characterize the digraphs that have a quasi-upward planar drawing. Second, we give a polynomial time algorithm for computing ``optimal' quasi-upward planar drawings within a given planar embedding. Further, we apply branch and bound techniques to the problem of computing optimal quasi-upward planar drawings, considering all possible planar embeddings. The paper also contains experimental results about the proposed techniques.     

Graph-based induction as a unified learning framework

We describe a graph-based induction algorithm that extracts typical patterns from colored digraphs. The method is shown to be capable of solving a variety of learning problems by mapping the different learning problems into colored digraphs. The generality and scope of this method can be attributed to the expressiveness of the colored digraph representation, which allows a number of different learning problems to be solved by a single algorithm. We demonstrate the application of our method to two seemingly different learning tasks: inductive learning of classification rules, and learning macro rules for speeding up inference. We also show that the uniform treatment of these two learning tasks enables our method to solve complex learning problems such as the construction of hierarchical knowledge bases.     

Consensus tracking control of discrete‐time second‐order agents over switching signed digraphs with arbitrary antagonistic relations

This article studies the problem of consensus tracking control for second‐order agents in multiagent systems over switching signed digraphs. Compared with the existing consensus tracking works on the structurally balanced signed digraph where the antagonistic relations exist only between two independent subgroups, this article explores a more general case for the first time, in the sense that the antagonistic relation is allowed between any two agents. On the basis of the design of a cooperation‐antagonism environment‐based distributed algorithm, suitable model transformation vectors are utilized to convert the stability of original system into a product convergence problem of time‐varying superstochastic matrices. By analyzing the convergence, algebraic conditions between positive and negative weights are established to ensure that all followers can eventually reach the leader's state under switching signed digraphs with arbitrary antagonistic relations. Simulation examples are provided to demonstrate the effectiveness of our results.     

On characterization of periodic digraphs

We investigate the problem of describing subgraphs of periodic digraphs. A necessary and sufficient condition is obtained for a digraph to be a subgraph of a periodic digraph.Translated from Kibernetika, No. 1, pp. 41–44, January–February, 1989.     

Efficient similarity search within user-specified projective subspaces

Many applications — such as content-based image retrieval, subspace clustering, and feature selection — may benefit from efficient subspace similarity search. Given a query object, the goal of subspace similarity search is to retrieve the most similar objects from the database, where the similarity distance is defined over an arbitrary subset of dimensions (or features) — that is, an arbitrary axis-aligned projective subspace — specified along with the query. Though much effort has been spent on similarity search in fixed subspaces, relatively little attention has been given to the problem of similarity search when the dimensions are specified at query time. In this paper, we propose new methods for the subspace similarity search problem for real-valued data. Extensive experiments are provided showing very competitive performance relative to state-of-the-art solutions.     

On legal path problems in digraphs

In this paper we consider the problem of finding a legal source to sink (s-t) path in a digraph G = (V, E), for which a set of impossible paths is specified. This problem arises in program testing. An efficient algorithm is presented for the case when G is an acyclic digraph and the general problem is shown to be computationally intractable.