Acyclic Edge Coloring of Triangle-Free Planar Graphs

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, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G) ? ? + 2, where ? = ?(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|-1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a'(G) ? ? + 3. Triangle-free planar graphs satisfy Property A. We infer that a'(G) ? ? + 3, if G is a triangle-free planar graph. Another class of graph which satisfies Property A is 2-fold graphs (union of two forests). (C) 2011 Wiley Periodicals, Inc. J Graph Theory

Nonuniform random geometric graphs with location-dependent radii

We propose a distribution-free approach to the study of random geometric graphs. The distribution of vertices follows a Poisson point process with intensity function n f(center dot), where n is an element of N, and f is a probability density function on R-d. A vertex located at x connects via directed edges to other vertices that are within a cut-off distance r(n)(x). We prove strong law results for (i) the critical cut-off function so that almost surely, the graph does not contain any node with out-degree zero for sufficiently large n and (ii) the maximum and minimum vertex degrees. We also provide a characterization of the cut-off function for which the number of nodes with out-degree zero converges in distribution to a Poisson random variable. We illustrate this result for a class of densities with compact support that have at most polynomial rates of decay to zero. Finally, we state a sufficient condition for an enhanced version of the above graph to be almost surely connected eventually.

Computing Reeb Graphs as a Union of Contour Trees

The Reeb graph of a scalar function tracks the evolution of the topology of its level sets. This paper describes a fast algorithm to compute the Reeb graph of a piecewise-linear (PL) function defined over manifolds and non-manifolds. The key idea in the proposed approach is to maximally leverage the efficient contour tree algorithm to compute the Reeb graph. The algorithm proceeds by dividing the input into a set of subvolumes that have loop-free Reeb graphs using the join tree of the scalar function and computes the Reeb graph by combining the contour trees of all the subvolumes. Since the key ingredient of this method is a series of union-find operations, the algorithm is fast in practice. Experimental results demonstrate that it outperforms current generic algorithms by a factor of up to two orders of magnitude, and has a performance on par with algorithms that are catered to restricted classes of input. The algorithm also extends to handle large data that do not fit in memory.

A constant factor approximation algorithm for boxicity of circular arc graphs

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in Rk. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n0.5-ε)-factor, for any ε > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an nε-factor approximation algorithm for computing boxicity is known, for any ε < 1. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a (2+ 1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k ≥ 1 is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n2) in both these cases and in O(mn+kn2) which is at most O(n3) time we also get their corresponding box representations, where n is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.

Efficient Regular Expression Pattern Matching for Network Intrusion Detection Systems using Modified Word-based Automata

Network Intrusion Detection Systems (NIDS) intercept the traffic at an organization's network periphery to thwart intrusion attempts. Signature-based NIDS compares the intercepted packets against its database of known vulnerabilities and malware signatures to detect such cyber attacks. These signatures are represented using Regular Expressions (REs) and strings. Regular Expressions, because of their higher expressive power, are preferred over simple strings to write these signatures. We present Cascaded Automata Architecture to perform memory efficient Regular Expression pattern matching using existing string matching solutions. The proposed architecture performs two stage Regular Expression pattern matching. We replace the substring and character class components of the Regular Expression with new symbols. We address the challenges involved in this approach. We augment the Word-based Automata, obtained from the re-written Regular Expressions, with counter-based states and length bound transitions to perform Regular Expression pattern matching. We evaluated our architecture on Regular Expressions taken from Snort rulesets. We were able to reduce the number of automata states between 50% to 85%. Additionally, we could reduce the number of transitions by a factor of 3 leading to further reduction in the memory requirements.

Analysing modifica-tions in the synthesis of multiple state mechanical devices using configuration space and topology graphs

Automated synthesis of mechanical designs is an important step towards the development of an intelligent CAD system. Research into methods for supporting conceptual design using automated synthesis has attracted much attention in the past decades. In our research, ten experimental studies are conducted to find out how designers synthesize solution concepts for multi-state mechanical devices. The designers are asked to think aloud, while carrying out the synthesis. These design synthesis processes are video recorded. It has been found that modification of kinematic pairs and mechanisms is the major activity carried out by all the designers. This paper presents an analysis of these synthesis processes using configuration space and topology graph to identify and classify the types of modifications that take place. Understanding of these modification processes and the context in which they happened is crucial to develop a system for supporting design synthesis of multiple state mechanical devices that is capable of creating a comprehensive variety of solution alternatives.

Asymptotic wavenumber expansions of a strongly orthotropic fluid-filled circular cylindrical shell

In this paper, a suitable nondimensional `orthotropy parameter' is defined and asymptotic expansions are found for the wavenumbers in in vacuo and fluid-filled orthotropic circular cylindrical shells modeled by the Donnell-Mushtari theory. Here, the elastic moduli in the two directions are greatly different; the particular case of E-x >> E-theta is studied in detail, i.e., the elastic modulus in the longitudinal direction is much larger than the elastic modulus in the circumferential direction. These results are compared with the corresponding results for a `slightly orthotropic' shell (E-x approximate to E-theta) and an isotropic shell. The novelty of this presentation lies in obtaining closed-form expansions for the in vacuo and coupled wavenumbers in an orthotropic shell using perturbation methods aiding in a better physical understanding of the problem.

Evidence of novel quasiparticles in a strongly interacting two-dimensional electron system: giant thermopower and metallic behaviour

We report thermopower (S) and electrical resistivity (rho (2DES) ) measurements in low-density (10(14) m(-2)), mesoscopic two-dimensional electron systems (2DESs) in GaAs/AlGaAs heterostructures at sub-Kelvin temperatures. We observe at temperatures a parts per thousand(2)0.7 K a linearly growing S as a function of temperature indicating metal-like behaviour. Interestingly this metallicity is not Drude-like, showing several unusual characteristics: (i) the magnitude of S exceeds the Mott prediction valid for non-interacting metallic 2DESs at similar carrier densities by over two orders of magnitude; and (ii) rho (2DES) in this regime is two orders of magnitude greater than the quantum of resistance h/e (2) and shows very little temperature-dependence. We provide evidence suggesting that these observations arise due to the formation of novel quasiparticles in the 2DES that are not electron-like. Finally, rho (2DES) and S show an intriguing decoupling in their density-dependence, the latter showing striking oscillations and even sign changes that are completely absent in the resistivity.

Some regularity theorems for CR mappings

The purpose of this article is to study Lipschitz CR mappings from an h-extendible (or semi-regular) hypersurface in . Under various assumptions on the target hypersurface, it is shown that such mappings must be smooth. A rigidity result for proper holomorphic mappings from strongly pseudoconvex domains is also proved.

Totally geodesic discs in strongly convex domains

We prove that every isometry from the unit disk Delta in , endowed with the Poincar, distance, to a strongly convex bounded domain Omega of class in , endowed with the Kobayashi distance, is the composition of a complex geodesic of Omega with either a conformal or an anti-conformal automorphism of Delta. As a corollary we obtain that every isometry for the Kobayashi distance, from a strongly convex bounded domain of class in to a strongly convex bounded domain of class in , is either holomorphic or anti-holomorphic.

Anisotropy induced crossover from weakly to strongly first order melting of two dimensional solids

Melting and freezing transitions in two dimensional (2D) systems are known to show highly unusual characteristics. Most of the earlier studies considered atomic systems: the melting of 2D molecular solids is still largely unexplored. In order to understand the role of anisotropy as well as multiple energy and length scales present in molecular systems, here we report computer simulation studies of melting of 2D molecular systems. We computed a limited portion of the solid-liquid phase diagram. We find that the interplay between the strength of isotropic and anisotropic interactions can give rise to rich phase diagram consisting of isotropic liquid and two crystalline phases-honeycomb and oblique. The nature of the transition depends on the relative strength of the anisotropic interaction and a strongly first order melting turns into a weakly first order transition on increasing the strength of the isotropic interaction. This crossover can be attributed to an increase in stiffness of the solid phase free energy minimum on increasing the strength of the anisotropic interaction. The defects involved in melting of molecular systems are quite different from those known for the atomic systems.

Growth-temperature dependent physical properties of SnS nanocrystalline thin films

In this article we have demonstrated the influence of growth-temperature on the morphology and orientation of SnS films deposited by thermal evaporation technique. While increasing the growth-temperature, the morphology of SnS films changed from flakes-like nanocrystals to regular cubes, whereas their orientation shifted from <111> to <040> direction. The chemical composition of SnS films gradually changed from sulfur-rich to tin-rich with the increase of growth-temperature. The structural analyzes reveal that the crystal structure of SnS films probably changes from orthorhombic to tetragonal at the growth-temperature of about 410 degrees C. Raman studies show that SnS films grown at all temperatures consist of purely SnS phase, whereas the optical studies reveal that the direct optical bandgap of SnS films decreased with the increase of growth-temperature. From these results it has been emphasized that the morphology and orientation along with electrical and optical properties of nearly stoichiometric SnS films strongly depend on their growth-temperature.

Product Dimension of Forests and Bounded Treewidth Graphs

The product dimension of a graph G is defined as the minimum natural number l such that G is an induced subgraph of a direct product of l complete graphs. In this paper we study the product dimension of forests, bounded treewidth graphs and k-degenerate graphs. We show that every forest on n vertices has product dimension at most 1.441 log n + 3. This improves the best known upper bound of 3 log n for the same due to Poljak and Pultr. The technique used in arriving at the above bound is extended and combined with a well-known result on the existence of orthogonal Latin squares to show that every graph on n vertices with treewidth at most t has product dimension at most (t + 2) (log n + 1). We also show that every k-degenerate graph on n vertices has product dimension at most inverted right perpendicular5.545 k log ninverted left perpendicular + 1. This improves the upper bound of 32 k log n for the same by Eaton and Rodl.

Rainbow colouring of split and threshold Graphs

A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every pair of vertices is connected by at least one path in which no two edges are coloured the same. Such a colouring using minimum possible number of colours is called an optimal rainbow colouring, and the minimum number of colours required is called the rainbow connection number of the graph. A Chordal Graph is a graph in which every cycle of length more than 3 has a chord. A Split Graph is a chordal graph whose vertices can be partitioned into a clique and an independent set. A threshold graph is a split graph in which the neighbourhoods of the independent set vertices form a linear order under set inclusion. In this article, we show the following: 1. The problem of deciding whether a graph can be rainbow coloured using 3 colours remains NP-complete even when restricted to the class of split graphs. However, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum. 2. For every integer k ≥ 3, the problem of deciding whether a graph can be rainbow coloured using k colours remains NP-complete even when restricted to the class of chordal graphs. 3. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Further, we can optimally rainbow colour a threshold graph in linear time.

Scalable flow-sensitive pointer analysis for fava with strong updates

The ability to perform strong updates is the main contributor to the precision of flow-sensitive pointer analysis algorithms. Traditional flow-sensitive pointer analyses cannot strongly update pointers residing in the heap. This is a severe restriction for Java programs. In this paper, we propose a new flow-sensitive pointer analysis algorithm for Java that can perform strong updates on heap-based pointers effectively. Instead of points-to graphs, we represent our points-to information as maps from access paths to sets of abstract objects. We have implemented our analysis and run it on several large Java benchmarks. The results show considerable improvement in precision over the points-to graph based flow-insensitive and flow-sensitive analyses, with reasonable running time.