Department of Computer Science and Engineering

Indian Institute of Technology Palakkad&nbsp;(IIT Palakkad or IIT PKD) is a public autonomous&nbsp;engineering&nbsp;and&nbsp;research&nbsp;institute located in&nbsp;Palakkad,&nbsp;Kerala. It was&nbsp;one of the five new&nbsp;IITs&nbsp;proposed in the&nbsp;2014 Union budget of India. The campus was inaugurated on 3 August 2015. The institute has 94 faculty, 978 students, and 63 non-teaching staffs.

IT Palakkad currently offers four-year Bachelor of Technology (B.Tech) and two years MS programmes in 8 different engineering disciplines including&nbsp;Computer Science, Electrical, Mechanical, Civil among others.

&nbsp;

IIT Palakkad

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges, so that every pair of vertices is connected by at least one path in which no two edges are colored the same. Our main result is that rc(G) ≤ [n/2] e for any 2-connected graph with at least three vertices. We conjecture that rc(G) ≤ n/k+ C for a _-connected graph G of order n, where C is a constant, and prove the conjecture for certain classes of graphs. We also prove that rc(G) ≤ (2 + ε)n/k+ 23= ε2 for any ε &gt; 0.

World University root node

Fulltext

Electronic Journal of Combinatorics

Rainbow connection number and connectivity

Based on a criterion of permutation polynomials of the form x rf(x q-1/m) by Wan and Lidl (1991) and some very elementary techniques we show existence of permutation binomials of the following forms (i) x(x 2n-1/3 + a) ∈ double-struck F 2n[x], for n &gt; 4 (ii) x 22n-1/2n-1+1 + ax = x 2n+2 + ax ∈ double-struck F 22n[x], for n ≥ 3. In (i), we extend a result of Carlitz (1962) for even characteristic. Moreover we present the count of such permutation binomials when a is in a certain subfield of double-struck F 2n. In (ii), we reprove, using much simpler technique, a recent result of Charpin and Kyureghyan (2008) and give the number of permutation binomials of this form. Finally, we discuss some cryptographic relevance of these results. © 2012 Springer-Verlag.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

On some permutation binomials of the form x 2n-1/k+1 + ax over double-struck F 2n: Existence and count

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. © 2012 Springer-Verlag.

Rainbow colouring of split and threshold graphs

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree δ, the rainbow connection number is upper bounded by 3n/(δ + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432-437), improving the previously best known bound of 20n/δ (J Graph Theory 63 (2010), 185-191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3n/(δ + 1) - 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree δ. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc(G), is upper bounded by c(G) + 2, where c(G) is the connected domination number of G. Bounds of the form diameter(G)&gt;rc(G)&gt;diameter(G) + c, 1&gt;c&gt;4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G)&gt;3̇radius(G). In most of these cases, we also demonstrate the tightness of the bounds. © 2011 Wiley Periodicals, Inc.

Journal of Graph Theory

Rainbow connection number and connected dominating sets

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour the edges of G, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this paper we show that for every connected graph G, with minimum degree at least 2, , where &nbsp;is the connected domination number of G. Bounds of the form , for many special graph classes follow as easy corollaries from this result. We also show that every bridge-less chordal graph G has . An extension of this idea to two-step dominating sets is used to show that for every connected graph on n vertices with minimum degree . This solves an open problem from Schiermeyer, 2009 [Schiermeyer, I.

Electronic Notes in Discrete Mathematics

Rainbow Connection Number and Connected Dominating Sets

Distributed Wireless Networks : Link Scheduling and Application Delay Modelling

In this paper, we study cyclic stabiliser codes over Fp of length dividing pt + 1 for some positive integer t. We call these t-Frobenius codes or just Frobenius codes for short. We give methods to construct them and show that they have efficient decoding algorithms. An important subclass of stabiliser codes are the linear stabiliser codes. For linear Frobenius codes we have stronger results: We completely characterise all linear Frobenius codes. As a consequence, we show that for every integer n that divides pt + 1 for an odd t, there are no linear cyclic codes of length n. On the other hand for even t, we give an explicit method to construct all of them. This gives us many explicit examples of Frobenius code which include the well studied Laflamme code. We show that the classical notion of BCH distance can be generalised to all the Frobenius codes that we construct, including the non-linear ones, and show that the algorithm of Berlekamp can be generalised to correct quantum errors within the BCH limit. This gives, for the first time, a family of codes that are neither CSS nor linear for which efficient decoding algorithm exits. © 2011 IEEE.

IEEE International Symposium on Information Theory - Proceedings

Quantum cyclic code of length dividing pt + 1

In this paper, we consider the problem of modelling the average delay in an IEEE 802.11 DCF wireless mesh network with a single root node under light traffic. We derive expression for mean delay for a co-located wireless mesh network, when packet generation is homogeneous Poisson process with rate . We also show how our analysis can be extended for non-homogeneous Poisson packet generation. We model mean delay by decoupling queues into independent M/M/1 queues. Extensive simulations are conducted to verify the analytical results. © 2011 IEEE.

ICCSP 2011 - 2011 International Conference on Communications and Signal Processing

Delay modelling for a single-hop wireless mesh network under light aggregate traffic

In this paper we study the suitability of the Metropolis Algorithm and its generalization for solving the shortest lattice vector problem (SVP). SVP has numerous applications spanning from robotics to computational number theory, viz., polynomial factorization. At the same time, SVP is a notoriously hard problem. Not only it is NP-hard, there is not even any polynomial approximation known for the problem that runs in polynomial time. What one normally uses is the LLL algorithm which, although a polynomial time algorithm, may give solutions which are an exponential factor away from the optimum. In this paper, we have defined an appropriate search space for the problem which we use for implementation of the Metropolis algorithm. We have defined a suitable neighbourhood structure which makes the diameter of the space polynomially bounded, and we ensure that each search point has only polynomially many neighbours. We can use this search space formulation for some other classes of evolutionary algorithms, e.g., for genetic and go-with-the-winner algorithms. We have implemented the Metropolis algorithm and Hasting's generalization of Metropolis algorithm for the SVP. Our results are quite encouraging in all instances when compared with LLL algorithm. © 2011 IEEE.

Proceedings of the 2011 11th International Conference on Hybrid Intelligent Systems, HIS 2011

Metropolis algorithm for solving Shortest lattice Vector Problem (SVP)

In this paper, we have proposed a novel architectural level simulation platform set-up to study the temperature characteristics of a processor system, when applying different speed scheduling schemes to execute the desired workload. Our simulation platform set-up is very practical as it combines the most practical simulation models, and uses the industry-standardized benchmark SPEC CPU2000 as the input to the platform. On this novel platform set-up we have compared two speed scheduling techniques, namely m-oscillation and a traditional optimal dynamic energy reducing speed scheduling technique, and have shown that m-oscillation can be as effective as the traditional approach in reducing the peak temperature of the system. © 2011 IEEE.