Drawing Planar Graphs Symmetrically, III: Oneconnected Planar Graphs

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. This paper discusses symmetric drawings of oneconnected planar graphs. More specifically, we discuss planar (geometric) automorphisms, that is, automorphisms of a graph G that can be represented as symmetries of a planar drawing of G. Finding planar automorphisms is the first and most difficult step in constructing planar symmetric drawings of graphs. The problem of determining whether a given graph has a nontrivial geometric automorphism is NP-complete for general graphs. The two previous papers in this series have discussed the problem of drawing planar graphs with a maximum number of symmetries, for the restricted cases where the graph is triconnected and biconnected. This paper extends the previous results to cover planar graphs that are oneconnected. We present a linear time algorithm for drawing oneconnected planar graphs with a maximum number of symmetries.     

Learning Bayesian Network Classifiers: Searching in a Space of Partially Directed Acyclic Graphs

There is a commonly held opinion that the algorithms for learning unrestricted types of Bayesian networks, especially those based on the score+search paradigm, are not suitable for building competitive Bayesian network-based classifiers. Several specialized algorithms that carry out the search into different types of directed acyclic graph (DAG) topologies have since been developed, most of these being extensions (using augmenting arcs) or modifications of the Naive Bayes basic topology. In this paper, we present a new algorithm to induce classifiers based on Bayesian networks which obtains excellent results even when standard scoring functions are used. The method performs a simple local search in a space unlike unrestricted or augmented DAGs. Our search space consists of a type of partially directed acyclic graph (PDAG) which combines two concepts of DAG equivalence: classification equivalence and independence equivalence. The results of exhaustive experimentation indicate that the proposed method can compete with state-of-the-art algorithms for classification.Editors: Pedro Larrañaga, Jose A. Lozano, Jose M. Peña and Iñaki Inza     

Determining the number of internal stability of a graph

The number of internal stability or independence number of an undirected graph has many important applications. Computationally it belongs to the class of intractable problems known as NP-Hard. In this paper we develop a tree search algorithm to determine the ndependence number of an undirected graph. Extensive computational experience on 2400 randomly generated graphs ranging from 20% to 90% densities and from 50 to 200 vertice has shown that the proposed algorithm is very effective.     

Signal transition graph constraints for synthesis of hazard-free asynchronous circuits with unbounded-gate delays

A synthesis procedure for asynchronous control circuits from a high level specification, signal transition graph (STG), is described. In this paper, we propose some syntactic constraints on STG to guarantee speed-independent implementation. We have introduced a global persistency concept in order to establish the relationship between the persistency concept introduced by Chu [2] (which we call local persistency) and the consistent state coding (CSC). The STG syntactic constraints required to compute theinput set of a signal are identified. This paper also describes an algorithm to ascertain whether a given STG has the CSC property. The algorithm identifies the non-persistent signals associated with the CSC violations. The algorithm has the advantage of operating directly on the STG rather than on the state graph.     

Data Mining in Large Databases Using Domain Generalization Graphs

Attribute-oriented generalization summarizes the information in a relational database by repeatedly replacing specific attribute values with more general concepts according to user-defined concept hierarchies. We introduce domain generalization graphs for controlling the generalization of a set of attributes and show how they are constructed. We then present serial and parallel versions of the Multi-Attribute Generalization algorithm for traversing the generalization state space described by joining the domain generalization graphs for multiple attributes. Based upon a generate-and-test approach, the algorithm generates all possible summaries consistent with the domain generalization graphs. Our experimental results show that significant speedups are possible by partitioning path combinations from the DGGs across multiple processors. We also rank the interestingness of the resulting summaries using measures based upon variance and relative entropy. Our experimental results also show that these measures provide an effective basis for analyzing summary data generated from relational databases. Variance appears more useful because it tends to rank the less complex summaries (i.e., those with few attributes and/or tuples) as more interesting.     

A database system of mechanical components based on geometric and topological similarity. Part I: representation

A database of mechanical components is an important issue for some manufacturing activities such as cost estimation, process planning, and design by case-based reasoning. In this paper, we give the representation scheme of the CAD model in such a database. Components are represented using attributed graphs in which the nodes correspond to the surfaces of the component and the links correspond to the edges of the component. The graph is based on the standard for the exchange of product information (STEP) physical file of the component. STEP file should be unique for a single component regardless of the underlying CAD system. The process of creating the graph of a component constitutes two sub-tasks: (i) importing the CAD model from the CAD system in STEP format and (ii) transforming the STEP data into attributed graph-based representation. The graph and its attributes describe the topology of the component completely together with some geometric data that are not dependent on any coordinate system such as surface type and curve type. These geometric data are helpful in the retrieval and matching processes in the database.     

High level synthesis of integrated heterogeneous pipelined processing elements for DSP applications

A technique for scheduling and processor allocation leading to the synthesis of integrated heterogeneous pipelined processing elements, implementing digital signal processing applications, is proposed. The proposed technique achieves efficient hardware implementations at the logic-level by minimizing the number of processing units used, without compromising the rate and delay optimality criteria.

The proposed algorithm is found to outperform algorithms resulting in homogeneous implementations, as it gives schedules with lower iteration periods, requires less hardware resources, and has lower time complexity at design time. In comparison with the already existing heterogeneous algorithms, the proposed algorithm produces schedules of lower time complexity and lower iteration period for some applications. The optimal performance of the proposed algorithm has been verified on several benchmarks.     

Efficient breadth first search on multi-GPU systems

Simple algorithms for the execution of a Breadth First Search on large graphs lead, running on clusters of GPUs, to a situation of load unbalance among threads and un-coalesced memory accesses, resulting in pretty low performances. To obtain a significant improvement on a single GPU and to scale by using multiple GPUs, we resort to a suitable combination of operations to rearrange data before processing them. We propose a novel technique for mapping threads to data that achieves a perfect load balance by leveraging prefix-sum and binary search operations. To reduce the communication overhead, we perform a pruning operation on the set of edges that needs to be exchanged at each BFS level. The result is an algorithm that exploits at its best the parallelism available on a single GPU and minimizes communication among GPUs. We show that a cluster of GPUs can efficiently perform a distributed BFS on graphs with billions of nodes.     

On the spectral radius of H-shape trees

A H-shape is a tree with exactly two of its vertices having maximal degree 3. In this paper, we show that 2≤λ₁ (H)<√ 5, where λ₁ (H) is the spectral radius of H.