On a game in directed graphs

Inspired by recent algorithms for electing a leader in a distributed system, we study the following game in a directed graph: each vertex selects one of its outgoing arcs (if any) and eliminates the other endpoint of this arc; the remaining vertices play on until no arcs remain. We call a directed graph lethal if the game must end with all vertices eliminated and mortal if it is possible that the game ends with all vertices eliminated. We show that lethal graphs are precisely collections of vertex-disjoint cycles, and that the problem of deciding whether or not a given directed graph is mortal is NP-complete (and hence it is likely that no “nice” characterization of mortal graphs exists).     

Past‐Free[ze] reachability analysis: reaching further with DAG‐directed exhaustive state‐space analysis

Model‐checking enables the automated formal verification of software systems through the explicit enumeration of all the reachable states. While this technique has been successfully applied to industrial systems, it suffers from the state‐space explosion problem because of the exponential growth in the number of states with respect to the number of interacting components. In this paper, we present a new reachability analysis algorithm, named Past‐Free[ze], that reduces the state‐space explosion problem by freeing parts of the state‐space from memory. This algorithm relies on the explicit isolation of the acyclic parts of the system before analysis. The parallel composition of these parts drives the reachability analysis, the core of all model‐checkers. During the execution, the past states of the system are freed from memory making room for more future states. To enable counter‐example construction, the past states can be stored on external storage. To show the effectiveness of the approach, the algorithm was implemented in the OBP Observation Engine and was evaluated both on a synthetic benchmark and on realistic case studies from automotive and aerospace domains. The benchmark, composed of 50 test cases, shows that in average, 75% of the state‐space can be dropped from memory thus enabling the exploration of up to 14 times more states than traditional approaches. Moreover, in some cases, the reachability analysis time can be reduced by up to 25%. In realistic settings, the use of Past‐Free[ze] enabled the exploration of a state‐space 4.5 times larger on the automotive case study, where almost 50% of the states are freed from memory. Moreover, this approach offers the possibility of analyzing an arbitrary number of interactions between the environment and the system‐under‐verification; for instance, in the case of the aerospace example, 1000 pilot/system interactions could be analyzed unraveling an 80 GB state‐space using only 10 GB of memory. Copyright © 2016 John Wiley & Sons, Ltd.     

Dominating sets in directed graphs

We consider the problem of incrementally computing a minimal dominating set of a directed graph after the insertion or deletion of a set of arcs. Earlier results have either focused on the study of the properties that minimum (not minimal) dominating sets preserved or lacked to investigate which update affects a minimal dominating set and in what ways. In this paper, we first show how to incrementally compute a minimal dominating set on arc insertions. We then reduce the case of computing a minimal dominating set on arc deletions to the case of insertions. Some properties on minimal dominating sets are provided to support the incremental strategy. Lastly, we give a new bound on the size of minimum dominating sets based on those results.     

A browser for directed graphs

A general-purpose browser for directed graphs is described. The browser provides operations to examine and edit graphs and to generate a layout for a graph automatically that minimizes edge crossings. Two layout algorithms were implemented. A hierarchical graph layout algorithm was found to be best for directed graphs. The graph browser also has facilities that allow it to be integrated with other applications (e.g. a program browser). These facilities and our experiences building a program call-graph browser are described.     

Optimization of hierarchical directed graphs

A machine- and language-independent representation for programs suitable for use within a compiler is presented. This representation is the hierarchical directed graph. Powerful code optimization techniques are presented in the context of this representation. An experimental optimizer has been built to validate the ideas discussed. The power of the representation is evident in the compactness of the code implementing the optimizations.     

Data schemata based on directed graphs

Rooted, labeled, directed graphs (RLDs) are taken as the basis for describing data structures. A constructive formalism is set up to describe RLDs, generate them by means of grammars, and carry out operations such as accessing nodes, inserting and deleting data items, and recognizing graph patterns. It is shown how the formalism can be translated into languages for data definition and data manipulation, of the type associated with data-base systems. The availability of the formalism allows a systematic development of such languages, and provides a method of incorporating consistency preconditions to structural operations and proving the correctness of the data structures that arise in using such languages.     

A technique for drawing directed graphs

A four-pass algorithm for drawing directed graphs is presented. The fist pass finds an optimal rank assignment using a network simplex algorithm. The seconds pass sets the vertex order within ranks by an iterative heuristic, incorporating a novel weight function and local transpositions to reduce crossings. The third pass finds optimal coordinates for nodes by constructing and ranking an auxiliary graph. The fourth pass makes splines to draw edges. The algorithm creates good drawings and is fast     

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.     

Syntax directed program editing

A syntax editor provides alternative ways for manipulating programs (as opposed to text). Although not a new idea it has made only slow inroads into editing. This is because implementation is not easy and because of many practical considerations in the use of an editor. This paper covers the design issues of a syntax editor with particular reference to on—SED. Examples of different options taken by other editors are included.     

Stabdump—a dump interpreter program to assist debugging

Program development can be greatly speeded by a dump analysis program which makes the state of a program more visible to the programmer. A single comprehensive analysis presenting as much of the relevant material in as concise a manner as possible has proved superior in use to the alternative of interactive analysis one item-at-a-time. The methods adopted in the STAB utility to achieve comprehensive and concise output are described. The system and compiler modifications necessary to support this type of system are discussed.     

Make — a program for maintaining computer programs

Good programmers break their projects into a number of pieces, each to be processed or compiled by a different chain of programs. After a set of changes is made, the series of actions that must be taken can be quite complex, and costly errors are frequently made. This paper describes a program that can keep track of the relationships between parts of a program, and issue the commands needed to make the parts consistent after changes are made. Make has been in use on UNIX

1 UNIX is a trademark of Bell Laboratories.

systems since 1975. The underlying idea is quite simple and can be adapted to many other environments.     

Convergent drawing for mutually connected directed graphs

Directed graphs are used to represent a variety of datasets, including friendship on social networking services (SNS), pathways of genes, and citations of research papers. Graph drawing is useful in representing such datasets. At the international conference on Information Visualization (IV), we have presented a convergent edge drawing and a node layout technique for tightly and mutually connected directed graphs. The edge drawing technique in the IV paper includes three features: ordinary bundling of edges connecting pairs of node clusters, convergence of multiple bundles that connect to the same node cluster, and shape adjustment of two bundles connecting the same pair of node clusters. In this paper, we present improved node layout and edge drawing techniques, which make our edge bundling more effective. This paper also introduces a case study with a directed paper citation graph dataset.vvvvv     

Topological additive numbering of directed acyclic graphs

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let D be a digraph and f   a labeling of its vertices with positive integers; denote by S(v)$S(v)$ the sum of labels over all neighbors of each vertex v. The labeling f is called topological additive numbering   if S(u)<S(v)$S(u)<S(v)$ for each arc (u,v)$(u,v)$ of the digraph. The problem asks to find the minimum number k for which D   has a topological additive numbering with labels belonging to {1,…,k}$\{1,\dots ,k\}$, denoted by _ηt(D)${\eta }_t(D)$.     

Efficient coding of labeled directed acyclic graphs

 We use an adaptation of the Prüfer code for trees to encode labeled directed acyclic graphs, which are often abbreviated to DAGs (or ADGs). In this paper, each DAG is assigned a unique DAG code, which allows an easy handling for several purposes. The set of all possible DAG codes (and therefore the set of all DAGs) for a fixed number of n vertices can be generated efficiently. Furthermore, we are able to rank DAGs, i.e., we provide an algorithm that assigns every DAG a unique number in the set {0,…,a _n −1}, where a _n is the cardinality of the set of labeled DAGs with n≥1 vertices, and we are able to unrank DAGs, which is the inverse operation. We also gain recurrence relations, which can be used to calculate a _n and a _n,q , i.e., the number of DAGs with n vertices and q edges. Finally, it is possible to generate, enumerate, rank and unrank DAGs with given number of edges and also DAGs with bounded indegree. RID="*" ID="*" This research was supported by the Austrian Science Fund (FWF), P13261-INF. I want to thank the reviewers, specially the one who suggested to add the algorithm for unranking DAG codes, for reading the paper very carefully and for the helpful comments.     

Distributed consensus filter on directed switching graphs

We consider distributed estimation on a directed graph with switching topologies. Motivated by a recent PI consensus filter, we modify the protocol and remove the requirement of bidirectional exchange of neighboring gains for fixed topologies. We then extend the protocol to switching topologies and propose a new hybrid consensus filter design. Convergence results under both balanced directed, and general directed graphs are given for switching graphs. Consensus error bounds are analytically derived in the case of time‐varying inputs. Satisfactory simulation results are shown. Copyright © 2014 John Wiley & Sons, Ltd.