New approximation algorithms for minimum cycle bases of graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time 0(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time 0(n(3+2/k)), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega)) bound. We also present a 2-approximation algorithm with O(m(omega) root n log n) expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Boxicity and cubicity of asteroidal triple free graphs

The boxicity of a graph G, denoted box(G), is the least integer d such that G is the intersection graph of a family of d-dimensional (axis-parallel) boxes. The cubicity, denoted cub(G), is the least dsuch that G is the intersection graph of a family of d-dimensional unit cubes. An independent set of three vertices is an asteroidal triple if any two are joined by a path avoiding the neighbourhood of the third. A graph is asteroidal triple free (AT-free) if it has no asteroidal triple. The claw number psi(G) is the number of edges in the largest star that is an induced subgraph of G. For an AT-free graph G with chromatic number chi(G) and claw number psi(G), we show that box(G) <= chi(C) and that this bound is sharp. We also show that cub(G) <= box(G)([log(2) psi(G)] + 2) <= chi(G)([log(2) psi(G)] + 2). If G is an AT-free graph having girth at least 5, then box(G) <= 2, and therefore cub(G) <= 2 [log(2) psi(G)] + 4. (c) 2010 Elsevier B.V. All rights reserved.

A Hardware Grid Simulator to Test Grid-Connected Inverter Systems.

Grid-connected systems when put to use at the site would experience scenarios like voltage sag, voltage swell, frequency deviations and unbalance which are common in the real world grid. When these systems are tested at laboratory, these scenarios do not exist and an almost stiff voltage source is what is usually seen. But, to qualify the grid-connected systems to operate at the site, it becomes essential to test them under the grid conditions mentioned earlier. The grid simulator is a hardware that can be programmed to generate some of the typical conditions experienced by the grid-connected systems at site. It is an inverter that is controlled to act like a voltage source in series with a grid impedance. The series grid impedance is emulated virtually within the inverter control rather than through physical components, thus avoiding the losses and the need for bulky reactive components. This paper describes the design of a grid simulator. Control implementation issues are highlighted in the experimental results.

A new class of separators and planarity of chordal graphs

We introduce a new class of clique separators, called base sets, for chordal graphs. Base sets of a chordal graph closely reflect its structure. We show that the notion of base sets leads to structural characterizations of planar k-trees and planar chordal graphs. Using these characterizations, we develop linear time algorithms for recognizing planar k-trees and planar chordal graphs. These algorithms are extensions of the Lexicographic_Breadth_First_Search algorithm for recognizing chordal graphs and are much simpler than the general planarity checking algorithm. Further, we use the notion of base sets to prove the equivalence of hamiltonian 2-trees and maximal outerplanar graphs.

On the complexity of finding stopping set size in Tanner Graphs

The problem of determining whether a Tanner graph for a linear block code has a stopping set of a given size is shown to be NT-complete.

Decision support requirements for intelligent operation of southern grid in India

Control centers (CC) play a very important role in power system operation. An overall view of the system with information about all existing resources and needs is implemented through SCADA (Supervisory control and data acquisition system) and an EMS (energy management system). As advanced technologies have made their way into the utility environment, the operators are flooded with huge amount of data. The last decade has seen extensive applications of AI techniques, knowledge-based systems, Artificial Neural Networks in this area. This paper focuses on the need for development of an intelligent decision support system to assist the operator in making proper decisions. The requirements for realization of such a system are recognized for the effective operation and energy management of the southern grid in India The application of Petri nets leading to decision support system has been illustrated considering 24 bus system that is a part of southern grid.

Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).

Computing complete test graphs for hierarchical systems

Conformance testing focuses on checking whether an implementation. under test (IUT) behaves according to its specification. Typically, testers are interested it? performing targeted tests that exercise certain features of the IUT This intention is formalized as a test purpose. The tester needs a "strategy" to reach the goal specified by the test purpose. Also, for a particular test case, the strategy should tell the tester whether the IUT has passed, failed. or deviated front the test purpose. In [8] Jeron and Morel show how to compute, for a given finite state machine specification and a test purpose automaton, a complete test graph (CTG) which represents all test strategies. In this paper; we consider the case when the specification is a hierarchical state machine and show how to compute a hierarchical CTG which preserves the hierarchical structure of the specification. We also propose an algorithm for an online test oracle which avoids a space overhead associated with the CTG.

Grid interfacing of a photovoltaic system using a chain cell converter

With the rapid development of photovoltaic system installations and increased number of grid connected power systems, it has become imperative to develop an efficient grid interfacing instrumentation suitable for photovoltaic systems ensuring maximum power transfer. The losses in the power converter play an important role in the overall efficiency of a PV system. Chain cell converter is considered to be efficient as compared to PWM converters due to lower switching losses, modularized circuit layout, reduced voltage rating of the converter switches, reduced EMI. The structure of separate dc sources in chain cell converter is well suited for photovoltaic systems as there will b several separate PV modules in the PV array which can act as an individual dc source. In this work, a single phase multilevel chain cell converter is used to interface the photovoltaic array to a single phase grid at a frequency of 50Hz. Control algorithms are developed for efficient interfacing of the PV system with grid and isolating the PV system from grid under faulty conditions. Digital signal processor TMS320F 2812 is used to implement the control algorithms developed and for the generation of other control signals.

Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

Let G - (V, E) be a weighted undirected graph having nonnegative edge weights. An estimate (delta) over cap (u, v) of the actual distance d( u, v) between u, v is an element of V is said to be of stretch t if and only if delta(u, v) <= (delta) over cap (u, v) <= t . delta(u, v). Computing all-pairs small stretch distances efficiently ( both in terms of time and space) is a well-studied problem in graph algorithms. We present a simple, novel, and generic scheme for all-pairs approximate shortest paths. Using this scheme and some new ideas and tools, we design faster algorithms for all-pairs t-stretch distances for a whole range of stretch t, and we also answer an open question posed by Thorup and Zwick in their seminal paper [J. ACM, 52 (2005), pp. 1-24].

Outward spherical solidification of a superheated melt with time dependent boundary flux

Short-time analytical solutions of solid and liquid temperatures and freezing front have been obtained for the outward radially symmetric spherical solidification of a superheated melt. Although results are presented here only for time dependent boundary flux, the method of solution can be used for other kinds of boundary conditions also. Later, the analytical solution has been compared with the numerical solution obtained with the help of a finite difference numerical scheme in which the grid points change with the freezing front position. An efficient method of execution of the numerical scheme has been discussed in details. Graphs have been drawn for the total solidification times and temperature distributions in the solid.

Constructing Reeb Graphs using Cylinder Maps

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. In this video, we describe a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Arcs in the Reeb graph are computed in the second step using a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The algorithm is also able to handle non-manifold domains.

Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

Efficient algorithms for domination and Hamilton circuit problems on permutation graphs

The domination and Hamilton circuit problems are of interest both in algorithm design and complexity theory. The domination problem has applications in facility location and the Hamilton circuit problem has applications in routing problems in communications and operations research.The problem of deciding if G has a dominating set of cardinality at most k, and the problem of determining if G has a Hamilton circuit are NP-Complete. Polynomial time algorithms are, however, available for a large number of restricted classes. A motivation for the study of these algorithms is that they not only give insight into the characterization of these classes but also require a variety of algorithmic techniques and data structures. So the search for efficient algorithms, for these problems in many classes still continues.A class of perfect graphs which is practically important and mathematically interesting is the class of permutation graphs. The domination problem is polynomial time solvable on permutation graphs. Algorithms that are already available are of time complexity O(n2) or more, and space complexity O(n2) on these graphs. The Hamilton circuit problem is open for this class.We present a simple O(n) time and O(n) space algorithm for the domination problem on permutation graphs. Unlike the existing algorithms, we use the concept of geometric representation of permutation graphs. Further, exploiting this geometric notion, we develop an O(n2) time and O(n) space algorithm for the Hamilton circuit problem.