NNN. S. Narayanaswamy

N. S. Narayanaswamy

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


N. S. Narayanaswamy has a total of 47 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Parameterized algorithms for the Steiner arborescence problem on a hypercube

    by Sugyani Mahapatra, Manikandan Narayanan, N. S. Narayanaswamy


  • Open Access

    Perfect Resolution of Strong Conflict-Free Colouring of Interval Hypergraphs

    by N. S. Narayanaswamy, S. M. Dhannya

    The \(k\) -Strong Conflict-Free ( \(k\) -SCF colouring problem seeks to find a colouring of the vertices of a hypergraph \(H\) using minimum number of colours so that in every hyperedge \(e\) of \(H\) , there are at least \(\min\{|e|,k\}\) vertices whose colours are different from that of all other vertices in \(e\) . In the case of interval hypergraphs, we present an exact \({\mathsf{P}}\) -time algorithm for the \(k\) -SCF problem thus solving an open problem posed in 2014. We achieve our results by showing that for any hypergraph, a \(k\) -SCF colouring is a proper colouring of a related simple graph which we refer to as a co-occurrence graph . We then show that a co-occurrence graph is obtained by identifying an induced subgraph of a second simple graph that we introduce, which we refer to as the conflict graph . For interval hypergraphs, we show that each co-occurrence graph and the conflict graph are perfect graphs. This property plays a crucial role in our polynomial time algorithm. Second, we show that for an interval hypergraph, the \(1\) -SCF colouring number is the minimum partition of its intervals into sets such that each set has an exact hitting set (a hitting set in which each interval is hit exactly once).


  • Open Access

    Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation

    by Girish Balakrishnan, Sankardeep Chakraborty, Seungbum Jo, N S Narayanaswamy, Kunihiko Sadakane

    Erdős and West (Discrete Mathematics'85) considered the class of $n$ vertex intersection graphs which have a {\em $d$-dimensional} {\em $t$-representation}, that is, each vertex of a graph in the class has an associated set consisting of at most $t$ $d$-dimensional axis-parallel boxes. In particular, for a graph $G$ and for each $d \geq 1$, they consider $i_d(G)$ to be the minimum $t$ for which $G$ has such a representation. For fixed $t$ and $d$, they consider the class of $n$ vertex labeled graphs for which $i_d(G) \leq t$, and prove an upper bound of $(2nt+\frac{1}{2})d \log n - (n - \frac{1}{2})d \log(4πt)$ on the logarithm of size of the class. In this work, for fixed $t$ and $d$ we consider the class of $n$ vertex unlabeled graphs which have a {\em $d$-dimensional $t$-representation}, denoted by $\mathcal{G}_{t,d}$. We address the problem of designing a succinct data structure for the class $\mathcal{G}_{t,d}$ in an attempt to generalize the relatively recent results on succinct data structures for interval graphs (Algorithmica'21). To this end, for each $n$ such that $td^2$ is in $o(n / \log n)$, we first prove a lower bound of $(2dt-1)n \log n - O(ndt \log \log n)$-bits on the size of any data structure for encoding an arbitrary graph that belongs to $\mathcal{G}_{t,d}$. We then present a $((2dt-1)n \log n + dt\log t + o(ndt \log n))$-bit data structure for $\mathcal{G}_{t,d}$ that supports navigational queries efficiently. Contrasting this data structure with our lower bound argument, we show that for each fixed $t$ and $d$, and for all $n \geq 0$ when $td^2$ is in $o(n/\log n)$ our data structure for $\mathcal{G}_{t,d}$ is succinct. As a byproduct, we also obtain succinct data structures for graphs of bounded boxicity (denoted by $d$ and $t = 1$) and graphs of bounded interval number (denoted by $t$ and $d=1$) when $td^2$ is in $o(n/\log n)$.

  • Open Access

    A faster algorithm for Vertex Cover parameterized by solution size

    by David G. Harris, N. S. Narayanaswamy

    We describe a new algorithm for vertex cover with runtime $O^*(1.25284^k)$, where $k$ is the size of the desired solution and $O^*$ hides polynomial factors in the input size. This improves over previous runtime of $O^*(1.2738^k)$ due to Chen, Kanj, & Xia (2010) standing for more than a decade. The key to our algorithm is to use a potential function which simultaneously tracks $k$ as well as the optimal value $\lambda$ of the vertex cover LP relaxation. This approach also allows us to make use of prior algorithms for Maximum Independent Set in bounded-degree graphs and Above-Guarantee Vertex Cover. The main step in the algorithm is to branch on high-degree vertices, while ensuring that both $k$ and $\mu = k - \lambda$ are decreased at each step. There can be local obstructions in the graph that prevent $\mu$ from decreasing in this process; we develop a number of novel branching steps to handle these situations.


  • Open Access

    Effective Parallelization of the Vehicle Routing Problem

    by Rajesh Pandian Muniasamy, Somesh Singh, Rupesh Nasre, N.S. Narayanaswamy

    Capacitated Vehicle Routing Problem (CVRP) is an important combinatorial optimization problem, which is also NP-hard. A wide array of heuristics have been proposed in the literature to obtain an approximate solution to CVRP. To improve the execution time, parallel methods have been developed for accelerating metaheuristics-based algorithms, genetic algorithms, and evolutionary algorithms for CVRP. Despite these advances, our experiments with the state-of-the-art parallel solutions indicate that their run times are too high to be practically useful. The combinatorial explosion is so high that the execution time is prohibitively large even on mid-sized CVRP instances having a few hundred customers. In this work, we propose a novel technique which combines local search and randomization for solving CVRP faster with reasonable accuracy, even on large problem instances. Our usage of randomization enables searching a large space of candidate solutions. We experimentally compare our proposed method with the state-of-the-art GPU implementations on diverse input instances and demonstrate the efficacy of our approach. Our sequential and shared-memory parallel implementations are on an average 36--1189× faster than the state-of-the-art GPU-parallel genetic algorithms while also achieving a superior solution quality. Furthermore, our reported solutions are close to the current best-known solutions from CVRPLIB.


  • Parameterized Complexity of Minimum Membership Dominating Set

    by Akanksha Agrawal, Pratibha Choudhary, N. S. Narayanaswamy, K. K. Nisha, Vijayaragunathan Ramamoorthi


  • Open Access

    Succinct Data Structure for Path Graphs

    by Girish Balakrishnan, Sankardeep Chakraborty, N S Narayanaswamy, Kunihiko Sadakane

    We consider the problem of designing a succinct data structure for {\it path graphs} (which are a proper subclass of chordal graphs and a proper superclass of interval graphs) on $n$ vertices while supporting degree, adjacency, and neighborhood queries efficiently. We provide the following two solutions for this problem: - an $n \log n+o(n \log n)$-bit succinct data structure that supports adjacency query in $O(\log n)$ time, neighborhood query in $O(d \log n)$ time and finally, degree query in $\min\{O(\log^2 n), O(d \log n)\}$ where $d$ is the degree of the queried vertex. - an $O(n \log^2 n)$-bit space-efficient data structure that supports adjacency and degree queries in $O(1)$ time, and the neighborhood query in $O(d)$ time where $d$ is the degree of the queried vertex. Central to our data structures is the usage of the classical heavy path decomposition by Sleator and Tarjan~\cite{ST}, followed by a careful bookkeeping using an orthogonal range search data structure using wavelet trees~\cite{Makinen2007} among others, which maybe of independent interest for designing succinct data structures for other graph classes.

  • Trade-Offs in Dynamic Coloring for Bipartite and General Graphs

    by Manas Jyoti Kashyop, N. S. Narayanaswamy, Meghana Nasre, Sai Mohith Potluri


  • An Invitation to Dynamic Graph Problems: Lower Bounds — III

    by Manas Jyoti Kashyop, N. S. Narayanaswamy