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

We derive a local criterion for a plane near-triangulated graph to be perfect. It is shown that a plane near-triangulated graph is perfect if and only if it does not contain either a vertex, an edge or a triangle, the neighbourhood of which has an odd hole as its boundary. The characterization leads to an O(n2) algorithm for checking perfectness of plane near-triangulations. © 2020 Elsevier B.V.

World University root node

Theoretical Computer Science

A local characterization for perfect plane near-triangulations

arXiv preprint arXiv:2005.

A Linear Time Algorithm for Computing the Eternal Vertex Cover Number of Cactus Graphs

B0 -VPG graphs are intersection graphs of vertical and horizontal line segments on a plane. Cohen, Golumbic, Trotter, and Wang [Order, 2016] pose the question of characterizing B0 -VPG permutation graphs. We respond here by characterizing B0 -VPG cocomparability graphs. This characterization also leads to a polynomial time recognition and B0 -VPG drawing algorithm for the class. Our B0 -VPG drawing algorithm starts by fixing any one of the many posets P whose cocomparability graph is the input graph G. The drawing we obtain not only visualizes G in that one can distinguish comparable pairs from incomparable ones, but one can also identify which among a comparable pair is larger in P from this visualization. © 2020, Springer Nature Switzerland AG.

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

Characterization and a 2D Visualization of B0 -VPG Cocomparability Graphs

Distributed Graph Analytics

Dynamic Graph Algorithms

GPU Architecture and Programming Challenges

Experiments, Evaluation and Future Directions

As the automotive industry is moving towards electric and self-driving vehicles, how to ensure the high degree of reliability for electronic control systems (ECS) has emerged as a serious concern. Temperature plays a vital role in the reliability of ECS because vehicles are subjected to high chip temperature due to harsh operating conditions and high integrated circuit (IC) on-chip power density. In this paper, we study the problem on how to optimize the lifetime reliability and guarantee the chip's peak temperature of ECS by judiciously allocating the application to ECS. We first propose a simple mathematical programming based thermal aware approach, assuming temperature can reach a stable status immediately. We then present a genetic algorithm approach based on effective and computationally efficient methods for peak temperature identification and system-wide lifetime reliability calculation, by taking advantage of the periodicity of vehicle applications. Our experimental results, based on both synthetic test cases and practical benchmarks demonstrate the significant improvement in lifetime reliability and CPU time for automotive ECS achieved by our proposed algorithms compared to the state-of-the-art results. © 2020 IEEE.

Proceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors

Thermal Aware Lifetime Reliability Optimization for Automotive Distributed Computing Applications

A graph is called a split graph if its vertex set can be partitioned into a clique and an independent set. Split graphs have rich mathematical structure and interesting algorithmic properties making it one of the most well-studied special graph classes. In the SPLIT VERTEX DELETION problem, given a graph and a positive integer k, the objective is to test whether there exists a subset of at most k vertices whose deletion results in a split graph. In this paper, we design a kernel for this problem with O(k2) vertices, improving upon the previous cubic bound known. Also, by giving a simple reduction from the VERTEX COVER problem, we establish that SPLIT VERTEX DELETION does not admit a kernel with O(k2−ϵ) edges, for any ϵ&gt;0, unless NP⊆coNP/poly. © 2020 Elsevier B.V.

Quadratic vertex kernel for split vertex deletion

The Path Cover and Cycle Cover problems are well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Here, we are given an undirected graph on n vertices and a positive integer r and the task is to check if there are r vertex-disjoint paths (cycles) that together visit all the vertices of the graph exactly once. Path Cover and Cycle Cover remain NP-hard even when restricted to chordal graphs (Information Processing Letters 1986) but are polynomial-time solvable on proper interval graphs (Discrete Mathematics 1993 and Proceedings of WADS 2019). In this paper, we study the complexity of Path Cover and Cycle Cover with respect to a structural parameter, namely, distance to proper interval graphs. In particular, we show that Path Cover and Cycle Cover are fixed-parameter tractable (FPT) when parameterized by k, the size of a proper interval deletion set (a set of vertices whose deletion results in a proper interval graph). For this purpose, we design an algorithm with O(2O ( k log k )nO ( 1 )) running time for each of these problems. Our algorithms use several interesting properties of proper interval graphs and a dynamic programming procedure over clique partitions to solve these problems in the mentioned time. As a consequence, we get the same fixed-parameter tractability results for Hamiltonian Cycle and Hamiltonian Path problems with the same parameterization. Recently, Chaplick et al. (Proceedings of WADS 2019) obtained polynomial kernels and compression algorithms for Path Cover and Cycle Cover parameterized by a different measure of similarity with proper interval graphs. Our FPT algorithms also adds to this study of structural parameterizations for these classical problems. © 2020, Springer Nature Switzerland AG.

Graph Hamiltonicity Parameterized by Proper Interval Deletion Set

This article studies the efficacy of the Metropolis algorithm for the minimum-weight codeword problem. The input is a linear code C given by its generator matrix and our task is to compute a nonzero codeword in the code C of least weight. In particular, we study the Metropolis algorithm on two possible search spaces for the problem: 1) the codeword space and 2) the generator space. The former is the space of all codewords of the input code and is the most natural one to use and hence has been used in previous work on this problem. The latter is the space of all generator matrices of the input code and is studied for the first time in this article. In this article, we show that for an appropriately chosen temperature parameter the Metropolis algorithm mixes rapidly when either of the search spaces mentioned above are used. Experimentally, we demonstrate that the Metropolis algorithm performs favorably when compared to previous attempts. When using the generator space, the Metropolis algorithm is able to outperform the previous algorithms in most of the cases. We have also provided both theoretical and experimental justification to show why the generator space is a worthwhile search space to use for this problem. © 1997-2012 IEEE.