Algorithmic aspects of k-tuple total domination in graphs

For a fixed positive integer k, a k-tuple total dominating set of a graph G = (V. E) is a subset T D-k of V such that every vertex in V is adjacent to at least k vertices of T Dk. In minimum k-tuple total dominating set problem (MIN k-TUPLE TOTAL DOM SET), it is required to find a k-tuple total dominating set of minimum cardinality and DECIDE MIN k-TUPLE TOTAL DOM SET is the decision version of MIN k-TUPLE TOTAL DOM SET problem. In this paper, we show that DECIDE MIN k-TUPLE TOTAL DOM SET is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that MIN k-TUPLE TOTAL DOM SET can be solved in polynomial time. We also propose some hardness results and approximation algorithms for MIN k-TUPLE TOTAL DOM SET problem. (c) 2012 Elsevier B.V. All rights reserved.

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

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.

NUcache: an efficient multicore cache organization based on next-use distance

The effectiveness of the last-level shared cache is crucial to the performance of a multi-core system. In this paper, we observe and make use of the DelinquentPC - Next-Use characteristic to improve shared cache performance. We propose a new PC-centric cache organization, NUcache, for the shared last level cache of multi-cores. NUcache logically partitions the associative ways of a cache set into MainWays and DeliWays. While all lines have access to the MainWays, only lines brought in by a subset of delinquent PCs, selected by a PC selection mechanism, are allowed to enter the DeliWays. The PC selection mechanism is an intelligent cost-benefit analysis based algorithm that utilizes Next-Use information to select the set of PCs that can maximize the hits experienced in DeliWays. Performance evaluation reveals that NUcache improves the performance over a baseline design by 9.6%, 30% and 33% respectively for dual, quad and eight core workloads comprised of SPEC benchmarks. We also show that NUcache is more effective than other well-known cache-partitioning algorithms.

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.

Analysis of distance relay trip regions for EHV and UHV transmission lines

This paper presents comparative evaluation of the distance relay characteristics for UHV and EHV transmission lines. Distance protection relay characteristics for the EHV and UHV systems are developed using Electromagnetic Transients (EMT) program. The variation of ideal trip boundaries for both the systems are presented. Unlike the conventional distance protection relay which uses a lumped parameter model, this paper uses the distributed parameter model. The effect of larger shunt susceptance on the trip boundaries is highlighted. Performance of distance relay with ideal trip boundaries for EHV and UHV lines have been tested for various fault locations and fault resistances. Electromagnetic Transients (EMT) program has been developed considering distributed parameter line model for simulating the test systems. The voltage and current phasors are computed from the signals using an improved full cycle DFT algorithm taking 20 samples per cycle. Two practical transmission systems of Indian power grid, namely 765 kV UHV transmission line and SREB 24-bus 400kV EHV system are used to test the performance of the proposed approach.

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.

Effect of fault resistance and grid short circuit MVA on impedance seen by distance relays on lines fed from wind turbine generating units (WTGU)

This paper deals with line protection challenges experienced in system having substantial wind generation penetration. Two types of WTGU: Doubly Fed (DFIG) and Squirrel Cage (SCIG) Induction Generators are simulated and connected to grid with single circuit transmission line. The paper summarizes analytical investigations carried out on the impedance seen by distance relays by varying fault resistances and grid short circuit MVA, for the protection of such transmission lines during faults. The results are also compared with systems having conventional synchronous machine connected to the grid.

On the SIG-dimension of trees under the L (a)-metric

Let where be a set of points in d-dimensional space with a given metric rho. For a point let r (p) be the distance of p with respect to rho from its nearest neighbor in Let B(p,r (p) ) be the open ball with respect to rho centered at p and having the radius r (p) . We define the sphere-of-influence graph (SIG) of as the intersection graph of the family of sets Given a graph G, a set of points in d-dimensional space with the metric rho is called a d-dimensional SIG-representation of G, if G is isomorphic to the SIG of It is known that the absence of isolated vertices is a necessary and sufficient condition for a graph to have a SIG-representation under the L (a)-metric in some space of finite dimension. The SIG-dimension under the L (a)-metric of a graph G without isolated vertices is defined to be the minimum positive integer d such that G has a d-dimensional SIG-representation under the L (a)-metric. It is denoted by SIG (a)(G). We study the SIG-dimension of trees under the L (a)-metric and almost completely answer an open problem posed by Michael and Quint (Discrete Appl Math 127:447-460, 2003). Let T be a tree with at least two vertices. For each let leaf-degree(v) denote the number of neighbors of v that are leaves. We define the maximum leaf-degree as leaf-degree(x). Let leaf-degree{(v) = alpha}. If |S| = 1, we define beta(T) = alpha(T) - 1. Otherwise define beta(T) = alpha(T). We show that for a tree where beta = beta (T), provided beta is not of the form 2 (k) - 1, for some positive integer k a parts per thousand yen 1. If beta = 2 (k) - 1, then We show that both values are possible.

Mutation analysis of the SLC4A11 gene in Indian families with congenital hereditary endothelial dystrophy 2 and a review of the literature

Purpose: Congenital hereditary endothelial dystrophy 2 (CHED2) is an autosomal recessive disorder caused by mutations in the solute carrier family 4, sodium borate transporter, member 11 (SLC4A11) gene. The purpose of this study was to identify the genetic cause of CHED2 in six Indian families and catalog all known mutations in the SLC4A11 gene. Methods: Peripheral blood samples were collected from individuals of the families with CHED2 and used in genomic DNA isolation. PCR primers were used to amplify the entire coding region including intron-exon junctions of SLC4A11. Amplicons were subsequently sequenced to identify the mutations. Results: DNA sequence analysis of the six families identified four novel (viz., p.Thr262Ile, p.Gly417Arg, p.Cys611Arg, and p.His724Asp) mutations and one known p.Arg869His homozygous mutation in the SLC4A11 gene. The mutation p.Gly417Arg was identified in two families. Conclusions: This study increases the mutation spectrum of the SLC4A11 gene. A review of the literature showed that the total number of mutations in the SLC4A11 gene described to date is 78. Most of the mutations are missense, followed by insertions-deletions. The present study will be helpful in genetic diagnosis of the families reported here.

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.

Polynomial time and parameterized approximation algorithms for boxicity

The boxicity (cubicity) of a graph G, denoted by box(G) (respectively cub(G)), is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (cubes) in ℝ k . The problem of computing boxicity (cubicity) is known to be inapproximable in polynomial time even for graph classes like bipartite, co-bipartite and split graphs, within an O(n 0.5 − ε ) factor for any ε > 0, unless NP = ZPP. We prove that if a graph G on n vertices has a clique on n − k vertices, then box(G) can be computed in time n22O(k2logk) . Using this fact, various FPT approximation algorithms for boxicity are derived. The parameter used is the vertex (or edge) edit distance of the input graph from certain graph families of bounded boxicity - like interval graphs and planar graphs. Using the same fact, we also derive an O(nloglogn√logn√) factor approximation algorithm for computing boxicity, which, to our knowledge, is the first o(n) factor approximation algorithm for the problem. We also present an FPT approximation algorithm for computing the cubicity of graphs, with vertex cover number as the parameter.

Game theoretic, decentralized, local information based algorithm for community detection in social graphs

Motivated by the observation that communities in real world social networks form due to actions of rational individuals in networks, we propose a novel game theory inspired algorithm to determine communities in networks. The algorithm is decentralized and only uses local information at each node. We show the efficacy of the proposed algorithm through extensive experimentation on several real world social network data sets.