Hardness results for computing optimal locally Gabriel graphs

Delaunay and Gabriel graphs are widely studied geo-metric proximity structures. Motivated by applications in wireless routing, relaxed versions of these graphs known as Locally Delaunay Graphs (LDGs) and Lo-cally Gabriel Graphs (LGGs) have been proposed. We propose another generalization of LGGs called Gener-alized Locally Gabriel Graphs (GLGGs) in the context when certain edges are forbidden in the graph. Unlike a Gabriel Graph, there is no unique LGG or GLGG for a given point set because no edge is necessarily in-cluded or excluded. This property allows us to choose an LGG/GLGG that optimizes a parameter of interest in the graph. We show that computing an edge max-imum GLGG for a given problem instance is NP-hard and also APX-hard. We also show that computing an LGG on a given point set with dilation ≤k is NP-hard. Finally, we give an algorithm to verify whether a given geometric graph G= (V, E) is a valid LGG.

On Locally Gabriel Geometric Graphs

Let be a set of points in the plane. A geometric graph on is said to be locally Gabriel if for every edge in , the Euclidean disk with the segment joining and as diameter does not contain any points of that are neighbors of or in . A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any , there exists LGG with edges. This improves upon the previous best bound of . (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any point set, there exists an independent set of size .

Modeling of a pressure modulated desalination system using bond graph methodology

A desalination system is a complex multi energy domain system comprising power/energy flow across several domains such as electrical, thermal, and hydraulic. The dynamic modeling of a desalination system that comprehensively addresses all these multi energy domains is not adequately addressed in the literature. This paper proposes to address the issue of modeling the various energy domains for the case of a single stage flash evaporation desalination system. This paper presents a detailed bond graph modeling of a desalination unit with seamless integration of the power flow across electrical, thermal, and hydraulic domains. The paper further proposes a performance index function that leads to the tracking of the optimal chamber pressure giving the optimal flow rate for a given unit of energy expended. The model has been validated in steady state conditions by simulation and experimentation.

Bond graph toolbox for handling complex variable

Bond graph is an apt modelling tool for any system working across multiple energy domains. Power electronics system modelling is usually the study of the interplay of energy in the domains of electrical, mechanical, magnetic and thermal. The usefulness of bond graph modelling in power electronic field has been realised by researchers. Consequently in the last couple of decades, there has been a steadily increasing effort in developing simulation tools for bond graph modelling that are specially suited for power electronic study. For modelling rotating magnetic fields in electromagnetic machine models, a support for vector variables is essential. Unfortunately, all bond graph simulation tools presently provide support only for scalar variables. We propose an approach to provide complex variable and vector support to bond graph such that it will enable modelling of polyphase electromagnetic and spatial vector systems. We also introduced a rotary gyrator element and use it along with the switched junction for developing the complex/vector variable's toolbox. This approach is implemented by developing a complex S-function tool box in Simulink inside a MATLAB environment This choice has been made so as to synthesise the speed of S-function, the user friendliness of Simulink and the popularity of MATLAB.

Flow-graph techniques for epicyclic gear train analysis

Flow-graph techniques are applied in this article for the analysis of an epicyclic gear train. A gear system based on this is designed and constructed for use in Numerical Control Systems.

Acoustic emission source location and damage detection in a metallic structure using a graph-theory-based geodesic pproach

A geodesic-based approach using Lamb waves is proposed to locate the acoustic emission (AE) source and damage in an isotropic metallic structure. In the case of the AE (passive) technique, the elastic waves take the shortest path from the source to the sensor array distributed in the structure. The geodesics are computed on the meshed surface of the structure using graph theory based on Dijkstra's algorithm. By propagating the waves in reverse virtually from these sensors along the geodesic path and by locating the first intersection point of these waves, one can get the AE source location. The same approach is extended for detection of damage in a structure. The wave response matrix of the given sensor configuration for the healthy and the damaged structure is obtained experimentally. The healthy and damage response matrix is compared and their difference gives the information about the reflection of waves from the damage. These waves are backpropagated from the sensors and the above method is used to locate the damage by finding the point where intersection of geodesics occurs. In this work, the geodesic approach is shown to be suitable to obtain a practicable source location solution in a more general set-up on any arbitrary surface containing finite discontinuities. Experiments were conducted on aluminum specimens of simple and complex geometry to validate this new method.

Bond graph model of doubly fed three phase induction motor using the Axis Rotator element for frame transformation

Induction motor is a typical member of a multi-domain, non-linear, high order dynamic system. For speed control a three phase induction motor is modelled as a d–q model where linearity is assumed and non-idealities are ignored. Approximation of the physical characteristic gives a simulated behaviour away from the natural behaviour. This paper proposes a bond graph model of an induction motor that can incorporate the non-linearities and non-idealities thereby resembling the physical system more closely. The model is validated by applying the linearity and idealities constraints which shows that the conventional ‘abc’ model is a special case of the proposed generalised model.

Topological properties of the one dimensional exponential random geometric graph

In this article we study the one-dimensional random geometric (random interval) graph when the location of the nodes are independent and exponentially distributed. We derive exact results and limit theorems for the connectivity and other properties associated with this random graph. We show that the asymptotic properties of a graph with a truncated exponential distribution can be obtained using the exponential random geometric graph. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008.

Optimal multicommodity flow through the complete graph with random edge capacities

We consider a multicommodity flow problem on a complete graph whose edges have random, independent, and identically distributed capacities. We show that, as the number of nodes tends to infinity, the maximumutility, given by the average of a concave function of each commodity How, has an almost-sure limit. Furthermore, the asymptotically optimal flow uses only direct and two-hop paths, and can be obtained in a distributed manner.

The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V, E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3. (C) 2010 Elsevier B.V. All rights reserved.

Macroscopic model of city traffic using bond graph modelling

Modelling of city traffic involves capturing of all the dynamics that exist in real-time traffic. Probabilistic models and queuing theory have been used for mathematical representation of the traffic system. This paper proposes the concept of modelling the traffic system using bond graphs wherein traffic flow is based on energy conservation. The proposed modelling approach uses switched junctions to model complex traffic networks. This paper presents the modelling, simulation and experimental validation aspects.

On the Nash-Williams′ Lemma in Graph Reconstruction Theory

A generalization of Nash-Williams′ lemma is proved for the Structure of m-uniform null (m − k)-designs. It is then applied to various graph reconstruction problems. A short combinatorial proof of the edge reconstructibility of digraphs having regular underlying undirected graphs (e.g., tournaments) is given. A type of Nash-Williams′ lemma is conjectured for the vertex reconstruction problem.

A polynomial bound on the number of light cycles in an undirected graph

Let G be an undirected graph with a positive real weight on each edge. It is shown that the number of minimum-weight cycles of G is bounded above by a polynomial in the number of edges of G. A similar bound holds if we wish to count the number of cycles with weight at most a constant multiple of the minimum weight of a cycle of G.

Analysing Message Sequence Graph Specifications

We give a detailed construction of a finite-state transition system for a com-connected Message Sequence Graph. Though this result is well-known in the literature and forms the basis for the solution to several analysis and verification problems concerning MSG specifications, the constructions given in the literature are either not amenable to implementation, or imprecise, or simply incorrect. In contrast we give a detailed construction along with a proof of its correctness. Our transition system is amenable to implementation, and can also be used for a bounded analysis of general (not necessarily com-connected) MSG specifications.