On the Cubicity of AT-Free Graphs and Circular-Arc Graphs

A unit cube in k dimensions (k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), a(i) + 1] on the real line. A graph G on n nodes is said to be representable as the intersection of k-cubes (cube representation in k dimensions) if each vertex of C can be mapped to a k-cube such that two vertices are adjacent in G if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G denoted as cub(G) is the minimum k for which G can be represented as the intersection of k-cubes. An interesting aspect about cubicity is that many problems known to be NP-complete for general graphs have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step. We give an O(bw . n) algorithm to compute the cube representation of a general graph G in bw + 1 dimensions given a bandwidth ordering of the vertices of G, where bw is the bandwidth of G. As a consequence, we get O(Delta) upper bounds on the cubicity of many well-known graph classes such as AT-free graphs, circular-arc graphs and cocomparability graphs which have O(Delta) bandwidth. Thus we have: 1. cub(G) <= 3 Delta - 1, if G is an AT-free graph. 2. cub(G) <= 2 Delta + 1, if G is a circular-arc graph. 3. cub(G) <= 2 Delta, if G is a cocomparability graph. Also for these graph classes, there axe constant factor approximation algorithms for bandwidth computation that generate orderings of vertices with O(Delta) width. We can thus generate the cube representation of such graphs in O(Delta) dimensions in polynomial time.

Biologically Inspired Cooperative Routing for Wireless Mobile Sensor Networks

Biological systems present remarkable adaptation, reliability, and robustness in various environments, even under hostility. Most of them are controlled by the individuals in a distributed and self-organized way. These biological mechanisms provide useful resources for designing the dynamical and adaptive routing schemes of wireless mobile sensor networks, in which the individual nodes should ideally operate without central control. This paper investigates crucial biologically inspired mechanisms and the associated techniques for resolving routing in wireless sensor networks, including Ant-based and genetic approaches. Furthermore, the principal contributions of this paper are as follows. We present a mathematical theory of the biological computations in the context of sensor networks; we further present a generalized routing framework in sensor networks by diffusing different modes of biological computations using Ant-based and genetic approaches; finally, an overview of several emerging research directions are addressed within the new biologically computational framework.

Bounding Run-Times of Local Adiabatic Algorithms

A common trick for designing faster quantum adiabatic algorithms is to apply the adiabaticity condition locally at every instant. However it is often difficult to determine the instantaneous gap between the lowest two eigenvalues, which is an essential ingredient in the adiabaticity condition. In this paper we present a simple linear algebraic technique for obtaining a lower bound on the instantaneous gap even in such a situation. As an illustration, we investigate the adiabatic un-ordered search of van Dam et al. [17] and Roland and Cerf [15] when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in log N, where N is the length of the unordered list) amount. We use our technique to derive a bound on the running time of a local adiabatic schedule in terms of the minimum gap between the lowest two eigenvalues.

d-Regular Graphs of Acyclic Chromatic Index at Least d+2

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Suclakov and Zaks (and earlier by Fiamcik) that a'(G) &lt;= Delta+2, where Delta = Delta(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require Delta+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d-regular graphs with 2n vertices and d&gt;n, requires at least d+2 colors. We also show that a'(K-n,K-n) &gt;= n+2, when n is odd using a more non-trivial argument. (Here K-n,K-n denotes the complete bipartite graph with n vertices on each side.) This lower bound for Kn,n can be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, n such that d &gt;= 5, n &gt;= 2d+3 and dn even, there exist d-regular graphs which require at least d+2-colors to be acyclically edge colored. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226-230, 2010.

Cluster based training for scaling non-linear support vector machines

Support Vector Machines(SVMs) are hyperplane classifiers defined in a kernel induced feature space. The data size dependent training time complexity of SVMs usually prohibits its use in applications involving more than a few thousands of data points. In this paper we propose a novel kernel based incremental data clustering approach and its use for scaling Non-linear Support Vector Machines to handle large data sets. The clustering method introduced can find cluster abstractions of the training data in a kernel induced feature space. These cluster abstractions are then used for selective sampling based training of Support Vector Machines to reduce the training time without compromising the generalization performance. Experiments done with real world datasets show that this approach gives good generalization performance at reasonable computational expense.

Nash equilibrium based semantic cache in mobile sensor grid database systems

Mobile applications are being increasingly deployed on a massive scale in various mobile sensor grid database systems. With limited resources from the mobile devices, how to process the huge number of queries from mobile users with distributed sensor grid databases becomes a critical problem for such mobile systems. While the fundamental semantic cache technique has been investigated for query optimization in sensor grid database systems, the problem is still difficult due to the fact that more realistic multi-dimensional constraints have not been considered in existing methods. To solve the problem, a new semantic cache scheme is presented in this paper for location-dependent data queries in distributed sensor grid database systems. It considers multi-dimensional constraints or factors in a unified cost model architecture, determines the parameters of the cost model in the scheme by using the concept of Nash equilibrium from game theory, and makes semantic cache decisions from the established cost model. The scenarios of three factors of semantic, time and locations are investigated as special cases, which improve existing methods. Experiments are conducted to demonstrate the semantic cache scheme presented in this paper for distributed sensor grid database systems.

On a Special Co-cycle Basis of Graphs

In this paper we consider the problems of computing a minimum co-cycle basis and a minimum weakly fundamental co-cycle basis of a directed graph G. A co-cycle in G corresponds to a vertex partition (S,V ∖ S) and a { − 1,0,1} edge incidence vector is associated with each co-cycle. The vector space over ℚ generated by these vectors is the co-cycle space of G. Alternately, the co-cycle space is the orthogonal complement of the cycle space of G. The minimum co-cycle basis problem asks for a set of co-cycles that span the co-cycle space of G and whose sum of weights is minimum. Weakly fundamental co-cycle bases are a special class of co-cycle bases, these form a natural superclass of strictly fundamental co-cycle bases and it is known that computing a minimum weight strictly fundamental co-cycle basis is NP-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory-Hu tree of the underlying undirected graph of G is a minimum co-cycle basis of G and it is also weakly fundamental.

Solution concepts in two-person multicriteria games

In this paper, we propose new solution concepts for multicriteria games and compare them with existing ones. The general setting is that of two-person finite games in normal form (matrix games) with pure and mixed strategy sets for the players. The notions of efficiency (Pareto optimality), security levels, and response strategies have all been used in defining solutions ranging from equilibrium points to Pareto saddle points. Methods for obtaining strategies that yield Pareto security levels to the players or Pareto saddle points to the game, when they exist, are presented. Finally, we study games with more than two qualitative outcomes such as combat games. Using the notion of guaranteed outcomes, we obtain saddle-point solutions in mixed strategies for a number of cases. Examples illustrating the concepts, methods, and solutions are included.

Approximate linear time ML decoding on tail-biting trellises in two rounds

A linear time approximate maximum likelihood decoding algorithm on tail-biting trellises is presented, that requires exactly two rounds on the trellis. This is an adaptation of an algorithm proposed earlier with the advantage that it reduces the time complexity from O(m log m) to O(m) where m is the number of nodes in the tail-biting trellis. A necessary condition for the output of the algorithm to differ from the output of the ideal ML decoder is deduced and simulation results on an AWGN channel using tail-biting trellises for two rate 1/2 convolutional codes with memory 4 and 6 respectively, are reported.

Dolezal's theorem revisited

This paper presents an improved version of Dolezal's theorem, in the area of linear algebra with continuously parametrized elements. An extension of the theorem is also presented, and applications of these results to system theory are indicated.

Multicriterion differential games with applications to combat problems

In this paper a theory for two-person zero sum multicriterion differential games is presented. Various solution concepts based upon the notions of Pareto optimality (efficiency), security and equilibrium are defined. These are shown to have interesting applications in the formulation and analysis of two target or combat differential games. The methods for obtaining outcome regions in the state space, feedback strategies for the players and the mode of play has been discussed in the framework of bicriterion zero sum differential games. The treatment is conceptual rather than rigorous.

On BCH codes over arbitrary integer rings

Bose-C-Hocquenghem (BCH) atdes with symbols from an arbitrary fhite integer ring are derived in terms of their generator polynomials. The derivation is based on the factohation of x to the power (n) - 1 over the unit ring of an appropriate extension of the fiite integer ring. lke eomtruetion is thus shown to be similar to that for BCH codes over fink flelda.

Broad-Band Coupling of High-Q Resonant Loads

Considering the method of broad-band coupling a series resonant RLC load to a resistive source using a uniform quarter-wave transmission-line inverter, it is shown that the 3-dB bandwidth of the network insertion loss reckoned with respect to a 0-dB loss attains a maximum for a particular value of the center frequency insertion loss in the range 0-3 dB. The center frequency Ioss and the corresponding value of the maximum 3-dB bandwidth are calculated for various loads and the results graphically presented.

Optimal infinite-horizon feedback laws for a general class of constrained discrete-time systems: stability and moving-horizon approximations

Stability results are given for a class of feedback systems arising from the regulation of time-varying discrete-time systems using optimal infinite-horizon and moving-horizon feedback laws. The class is characterized by joint constraints on the state and the control, a general nonlinear cost function and nonlinear equations of motion possessing two special properties. It is shown that weak conditions on the cost function and the constraints are sufficient to guarantee uniform asymptotic stability of both the optimal infinite-horizon and movinghorizon feedback systems. The infinite-horizon cost associated with the moving-horizon feedback law approaches the optimal infinite-horizon cost as the moving horizon is extended.

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.