Source author record

Jasine Babu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics Data Structures and Algorithms math.CO Computational Geometry

Catalog footprint

Research overview

12works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Eternal vertex cover number of maximal outerplanar graphs

Eternal vertex cover problem is a variant of the classical vertex cover problem modeled as a two player attacker-defender game. Computing eternal vertex cover number of graphs is known to be NP-hard in general and the complexity status of the problem for bipartite graphs is open. There is a quadratic complexity algorithm known for this problem for chordal graphs. Maximal outerplanar graphs forms a subclass of chordal graphs, for which no algorithm of sub-quadratic time complexity is known. In this paper, we obtain a recursive algorithm of linear time for computing eternal vertex cover number of maximal outerplanar graphs.

preprint2020arXiv

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

The eternal vertex cover problem is a dynamic variant of the classical vertex cover problem. It is NP-hard to compute the eternal vertex cover number of graphs and known algorithmic results for the problem are very few. This paper presents a linear time recursive algorithm for computing the eternal vertex cover number of cactus graphs. Unlike other graph classes for which polynomial time algorithms for eternal vertex cover number are based on efficient computability of a known lower bound directly derived from minimum vertex cover, we show that it is a certain substructure property that helps the efficient computation of eternal vertex cover number of cactus graphs. An extension of the result to graphs in which each block is an edge, a cycle or a biconnected chordal graph is also presented.

preprint2020arXiv

A local characterization for perfect plane near-triangulations

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(n^2)$ algorithm for checking perfectness of plane near-triangulations.

preprint2020arXiv

A new lower bound for eternal vertex cover number

We obtain a new lower bound for the eternal vertex cover number of an arbitrary graph $G$ , in terms of the cardinality of a vertex cover of minimum size in $G$ containing all its cut vertices. The consequences of the lower bound includes a quadratic time algorithm for computing the eternal vertex cover number of chordal graphs.

preprint2020arXiv

A Note on Arc-Disjoint Cycles in Bipartite Tournaments

We show that for each non-negative integer k, every bipartite tournament either contains k arc-disjoint cycles or has a feedback arc set of size at most 7(k - 1).

preprint2020arXiv

An Improvement to Chvátal and Thomassen's Upper Bound for Oriented Diameter

An orientation of an undirected graph $G$ is an assignment of exactly one direction to each edge of $G$ . The oriented diameter of a graph $G$ is the smallest diameter among all the orientations of $G$ . The maximum oriented diameter of a family of graphs $\mathscr{F}$ is the maximum oriented diameter among all the graphs in $\mathscr{F}$ . Chvátal and Thomassen [JCTB, 1978] gave a lower bound of $\frac{1}{2}d^2+d$ and an upper bound of $2d^2+2d$ for the maximum oriented diameter of the family of $2$ -edge connected graphs of diameter $d$ . We improve this upper bound to $1.373 d^2 + 6.971d-1$ , which outperforms the former upper bound for all values of $d$ greater than or equal to $8$ . For the family of $2$ -edge connected graphs of diameter $3$ , Kwok, Liu and West [JCTB, 2010] obtained improved lower and upper bounds of $9$ and $11$ respectively. For the family of $2$ -edge connected graphs of diameter $4$ , the bounds provided by Chvátal and Thomassen are $12$ and $40$ and no better bounds were known. By extending the method we used for diameter $d$ graphs, along with an asymmetric extension of a technique used by Chvátal and Thomassen, we have improved this upper bound to $21$ .

preprint2015arXiv

Sublinear Approximation Algorithms for Boxicity and Related Problems

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes in $\mathbb{R}^k$ . Cubicity is a variant of boxicity, where the axis parallel boxes in the intersection representation are restricted to be of unit length sides. Deciding whether boxicity (resp. cubicity) of a graph is at most k is NP-hard, even for k=2 or 3. Computing these parameters is inapproximable within $O(n^{1 - ε})$ -factor, for any $ε>0$ in polynomial time unless NP=ZPP, even for many simple graph classes. In this paper, we give a polynomial time $κ(n)$ factor approximation algorithm for computing boxicity and a $κ(n)\lceil \log \log n\rceil$ factor approximation algorithm for computing the cubicity, where $κ(n) =2\left\lceil\frac{n\sqrt{\log \log n}}{\sqrt{\log n}}\right\rceil$ . These o(n) factor approximation algorithms also produce the corresponding box (resp. cube) representations. As a special case, this resolves the question paused by Spinrad about polynomial time construction of o(n) dimensional box representations for boxicity 2 graphs. Other consequences of our approximation algorithm include $O(κ(n))$ factor approximation algorithms for computing the following parameters: the partial order dimension of finite posets, the interval dimension of finite posets, minimum chain cover of bipartite graphs, threshold dimension of split graphs and Ferrer's dimension of digraphs. Each of these parameters is inapproximable within an $O(n^{1 - ε})$ -factor, for any $ε>0$ in polynomial time unless NP=ZPP and the algorithms we derive seem to be the first o(n) factor approximation algorithms known for all these problems.

preprint2014arXiv

2-connecting Outerplanar Graphs without Blowing Up the Pathwidth

Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). This settles an open problem raised by Biedl, in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl for 2-vertex-connected outerplanar graphs will work for all outer planar graphs.

preprint2014arXiv

Approximating the Cubicity of Trees

Cubicity of a graph $G$ is the smallest dimension $d$ , for which $G$ is a unit disc graph in ${\mathbb{R}}^d$ , under the $l^\infty$ metric, i.e. $G$ can be represented as an intersection graph of $d$ -dimensional (axis-parallel) unit hypercubes. We call such an intersection representation a $d$ -dimensional cube representation of $G$ . Computing cubicity is known to be inapproximable in polynomial time, within an $O(n^{1-ε})$ factor for any $ε>0$ , unless NP=ZPP. In this paper, we present a randomized algorithm that runs in polynomial time and computes cube representations of trees, of dimension within a constant factor of the optimum. It is also shown that the cubicity of trees can be approximated within a constant factor in deterministic polynomial time, if the cube representation is not required to be computed. As far as we know, this is the first constant factor approximation algorithm for computing the cubicity of trees. It is not yet clear whether computing the cubicity of trees is NP-hard or not.

preprint2014arXiv

Parameterized and Approximation Algorithms for Boxicity

Boxicity of a graph $G(V,$ $E)$ , denoted by $box(G)$ , is the minimum integer $k$ such that $G$ can be represented as the intersection graph of axis parallel boxes in $\mathbb{R}^k$ . The problem of computing boxicity is inapproximable even for graph classes like bipartite, co-bipartite and split graphs within $O(n^{1 - ε})$ -factor, for any $ε>0$ in polynomial time unless $NP=ZPP$ . We give FPT approximation algorithms for computing the boxicity of graphs, where the parameter used is the vertex or edge edit distance of the given graph from families of graphs of bounded boxicity. This can be seen as a generalization of the parameterizations discussed in \cite{Adiga2}. Extending the same idea in one of our algorithms, we also get an $O\left(\frac{n\sqrt{\log \log n}}{\sqrt{\log n}}\right)$ factor approximation algorithm for computing boxicity and an $O\left(\frac{n {(\log \log n)}^{\frac{3}{2}}}{\sqrt{\log n}}\right)$ factor approximation algorithm for computing the cubicity. These seem to be the first $o(n)$ factor approximation algorithms known for both boxicity and cubicity. As a consequence of this result, a $o(n)$ factor approximation algorithm for computing the partial order dimension of finite posets and a $o(n)$ factor approximation algorithm for computing the threshold dimension of split graphs would follow.

preprint2012arXiv

Fixed-Orientation Equilateral Triangle Matching of Point Sets

Given a point set $P$ and a class $\mathcal{C}$ of geometric objects, $G_\mathcal{C}(P)$ is a geometric graph with vertex set $P$ such that any two vertices $p$ and $q$ are adjacent if and only if there is some $C \in \mathcal{C}$ containing both $p$ and $q$ but no other points from $P$ . We study $G_{\bigtriangledown}(P)$ graphs where $\bigtriangledown$ is the class of downward equilateral triangles (ie. equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half- $Θ_6$ graphs and TD-Delaunay graphs. The main result in our paper is that for point sets $P$ in general position, $G_{\bigtriangledown}(P)$ always contains a matching of size at least $\lceil\frac{n-2}{3}\rceil$ and this bound cannot be improved above $\lceil\frac{n-1}{3}\rceil$ . We also give some structural properties of $G_{\davidsstar}(P)$ graphs, where $\davidsstar$ is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of $G_{\davidsstar}(P)$ is simply a path. Through the equivalence of $G_{\davidsstar}(P)$ graphs with $Θ_6$ graphs, we also derive that any $Θ_6$ graph can have at most $5n-11$ edges, for point sets in general position.

preprint2011arXiv

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 rectangles in $\mathbf{R}^k$ . 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(n^{0.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+\frac{1}{k})$ -factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where $k \ge 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+n^2)$ in both these cases and in $O(mn+kn^2)= O(n^3)$ 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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jasine Babu

Research overview

Is this your work?

12 publications

Eternal vertex cover number of maximal outerplanar graphs

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

A local characterization for perfect plane near-triangulations

A new lower bound for eternal vertex cover number

A Note on Arc-Disjoint Cycles in Bipartite Tournaments

An Improvement to Chvátal and Thomassen's Upper Bound for Oriented Diameter

Sublinear Approximation Algorithms for Boxicity and Related Problems

2-connecting Outerplanar Graphs without Blowing Up the Pathwidth

Approximating the Cubicity of Trees

Parameterized and Approximation Algorithms for Boxicity

Fixed-Orientation Equilateral Triangle Matching of Point Sets

A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs

See the researcher in context

Building this map preview