Source author record

Sandip Das

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO Computational Geometry Data Structures and Algorithms Networking and Internet Architecture physics.flu-dyn Computer Science and Game Theory

Catalog footprint

Research overview

20works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On clique numbers of colored mixed graphs

An (m,n)-colored mixed graph, or simply, an (m,n)-graph is a graph having m different types of arcs and n different types of edges. A homomorphism of an (m,n)-graph G to another (m,n)-graph H is a vertex mapping that preserves adjacency, the type thereto and the direction. A subset R of the set of vertices of G that always maps distinct vertices in itself to distinct image vertices under any homomorphism is called an (m,n)-relative clique of G. The maximum cardinality of an (m,n)-relative clique of a graph is called the (m,n)-relative clique number of the graph. In this article, we explore the (m,n)-relative clique numbers for various families of graphs.

preprint2022arXiv

Schedulers Synchronization Supporting Ultra Reliable Low Latency Communications (URLLC) in Cloud-RAN over Virtualised Mesh PON

We propose a mechanism to support URLLC Open-RAN ultra-low latency over a MESH-PON, serving dense deployment of small cell and MEC nodes in an access network. We show the possibility, under given assumptions, to achieve application-to-application end-to-end latency below 1ms.

preprint2021arXiv

Frequency power spectra of global quantities in magnetoconvection

We present the results of direct numerical simulations of power spectral densities for kinetic energy, convective entropy and heat flux for unsteady Rayleigh-Bénard magnetoconvection in the frequency space. For larger values of frequency, the power spectral densities for all the global quantities vary with frequency $f$ as $f^{-2}$ . The scaling exponent is independent of Rayleigh number, Chandrasekhar's number and thermal Prandtl number.

preprint2021arXiv

Pseudoline arrangement graphs: degree sequences and eccentricities

A pseudoline arrangement graph is a planar graph induced by an embedding of a (simple) pseudoline arrangement. We study the corresponding graph realization problem and properties of pseudoline arrangement graphs. In the first part, we give a simple criterion based on the degree sequence that says whether a degree sequence will have a pseudoline arrangement graph as one of its realizations. In the second part, we study the eccentricities of vertices in such graphs. We observe that the diameter (maximum eccentricity of a vertex in the graph) of any pseudoline arrangement graph on $n$ pseudolines is $n-2$ . Then we characterize the diametrical vertices (whose eccentricity is equal to the graph diameter) of pseudoline arrangement graphs. These results hold for line arrangement graphs as well.

preprint2020arXiv

Algorithms and complexity for geodetic sets on planar and chordal graphs

We study the complexity of finding the \emph{geodetic number} on subclasses of planar graphs and chordal graphs. A set $S$ of vertices of a graph $G$ is a \emph{geodetic set} if every vertex of $G$ lies in a shortest path between some pair of vertices of $S$ . The \textsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality of a given graph. The problem is known to remain NP-hard on bipartite graphs, chordal graphs, planar graphs and subcubic graphs. We first study \textsc{MGS} on restricted classes of planar graphs: we design a linear-time algorithm for \textsc{MGS} on solid grids, improving on a $3$ -approximation algorithm by Chakraborty et al. (CALDAM, 2020) and show that it remains NP-hard even for subcubic partial grids of arbitrary girth. This unifies some results in the literature. We then turn our attention to chordal graphs, showing that \textsc{MGS} is fixed parameter tractable for inputs of this class when parameterized by its \emph{tree-width} (which equals its clique number). This implies a polynomial-time algorithm for $k$ -trees, for fixed $k$ . Then, we show that \textsc{MGS} is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012). As interval graphs are very constrained, to prove the latter result we design a rather sophisticated reduction technique to work around their inherent linear structure.

preprint2020arXiv

PON Virtualisation with EAST-WEST Communications for Low-Latency Converged Multi-Access Edge Computing (MEC)

We propose a virtual-PON based Mobile Fronthaul (MFH) architecture that allows direct communications between edge points (enabling EAST-WEST communication). Dynamic slicing improves service multiplexing while supporting ultra-low latency under 100 $μ$ s between cells and MEC nodes.

preprint2020arXiv

Thermal flux in unsteady Rayleigh-Bénard magnetoconvection

We present results of numerical investigation on thermal flux in Rayleigh-Bénard magnetoconvection in the presence of a uniform vertical magnetic field. We have studied thermal flux in different viscous fluids with a range of Prandtl number ( $0.1 \le \mathrm{Pr} < 6.5$ ) and a range of Chandrasekhar number ( $50 \le \mathrm{Q} \le 2.5 \times 10^4$ ). The power spectral density of the Nusselt number varies with frequency $f$ approximately as $f^{-2}$ . The probability distribution function of the fluctuating part of the Nusselt number is nearly normal distribution with slight asymmetric tails. For a fixed value the Rayleigh number $\mathrm{Ra}$ , the time averaged Nusselt number $\langle \mathrm{Nu} (\mathrm{Q})\rangle$ decreases logarithmically with Chandrasekhar number for $\mathrm{Q} > \mathrm{Q}_c$ , which depends on $\mathrm{Ra}$ and $\mathrm{Pr}$ . The reduced Nusselt number $\mathrm{Nu_r}$ $=$ $\langle \mathrm{Nu}(\mathrm{Q})\rangle/{\langle \mathrm{Nu}(0)\rangle}$ rises sharply, reaches a maximum slightly above unity and then start decreasing very slowly to unity as the value of a dimensionless parameter $\sqrt{\mathrm{Ra/(Q~Pr)}}$ is raised. The probability distribution function of the local thermal flux in the vertical direction is found to be asymmetric and non-Gaussian with a cusp at its maximum.

preprint2016arXiv

Chromatic number of signed graphs with bounded maximum degree

A signed graph $(G, Σ)$ is a graph positive and negative ( $Σ$ denotes the set of negative edges). To re-sign a vertex $v$ of a signed graph $(G, Σ)$ is to switch the signs of the edges incident to $v$ . If one can obtain $(G, Σ')$ by re-signing some vertices of $(G, Σ)$ , then $(G, Σ) \equiv (G, Σ')$ . A signed graphs $(G, Σ)$ admits an homomorphism to $(H, Λ)$ if there is a sign preserving vertex mapping from $(G,Σ')$ to $(H, Λ)$ for some $(G, Σ) \equiv (G, Σ')$ . The signed chromatic number $χ_{s}( (G, Σ))$ of the signed graph $(G, Σ)$ is the minimum order (number of vertices) of a signed graph $(H, Λ)$ such that $(G, Σ)$ admits a homomorphism to $(H, Λ)$ . For a family $\mathcal{F}$ of signed graphs $χ_{s}(\mathcal{F}) = \text{max}_{(G,Σ) \in \mathcal{F}} χ_{s}( (G, Σ))$ . We prove $2^{Δ/2-1} \leq χ_s(\mathcal{G}_Δ) \leq (Δ-1)^2. 2^{(Δ-1)} +2$ for all $Δ\geq 3$ where $\mathcal{G}_Δ$ is the family of connected signed graphs with maximum degree $Δ$ . \end{abstract}

preprint2016arXiv

Geometric k-Center Problems with Centers Constrained to Two Lines

We consider the $k$ -center problem in which the centers are constrained to lie on two lines. Given a set of $n$ weighted points in the plane, we want to locate up to $k$ centers on two parallel lines. We present an $O(n\log^2 n)$ time algorithm, which minimizes the weighted distance from any point to a center. We then consider the unweighted case, where the centers are constrained to be on two perpendicular lines. Our algorithms run in $O(n\log^2 n)$ time also in this case.

preprint2016arXiv

Linear-Time Fitting of a $k$ -Step Function

Given a set of $n$ weighted points on the $x$ - $y$ plane, we want to find a step function consisting of $k$ horizontal steps such that the maximum vertical weighted distance from any point to a step is minimized. We solve this problem in $O(n)$ time when $k$ is a constant. Our approach relies on the prune-and-search technique, and can be adapted to design similar linear time algorithms to solve the line-constrained k-center problem and the size- $k$ histogram construction problem as well.

preprint2016arXiv

On a special class of boxicity 2 graphs

We define and study a class of graphs, called 2-stab interval graphs (2SIG), with boxicity 2 which properly contains the class of interval graphs. A 2SIG is an axes-parallel rectangle intersection graph where the rectangles have unit height (that is, length of the side parallel to $Y$ -axis) and intersects either of the two fixed lines, parallel to the $X$ -axis, distance $1+ε$ ( $0 < ε< 1$ ) apart. Intuitively, 2SIG is a graph obtained by putting some edges between two interval graphs in a particular rule. It turns out that for these kind of graphs, the chromatic number of any of its induced subgraphs is bounded by twice of its (induced subgraph) clique number. This shows that the graph, even though not perfect, is not very far from it. Then we prove similar results for some subclasses of 2SIG and provide efficient algorithm for finding their clique number. We provide a matrix characterization for a subclass of 2SIG graph.

preprint2016arXiv

On local structures of cubicity 2 graphs

A 2-stab unit interval graph (2SUIG) is an axes-parallel unit square intersection graph where the unit squares intersect either of the two fixed lines parallel to the $X$ -axis, distance $1 + ε$ ( $0 < ε< 1$ ) apart. This family of graphs allow us to study local structures of unit square intersection graphs, that is, graphs with cubicity 2. The complexity of determining whether a tree has cubicity 2 is unknown while the graph recognition problem for unit square intersection graph is known to be NP-hard. We present a polynomial time algorithm for recognizing trees that admit a 2SUIG representation.

preprint2016arXiv

The $p$ -Center Problem in Tree Networks Revisited

We present two improved algorithms for weighted discrete $p$ -center problem for tree networks with $n$ vertices. One of our proposed algorithms runs in $O(n \log n + p \log^2 n \log(n/p))$ time. For all values of $p$ , our algorithm thus runs as fast as or faster than the most efficient $O(n\log^2 n)$ time algorithm obtained by applying Cole's speed-up technique [cole1987] to the algorithm due to Megiddo and Tamir [megiddo1983], which has remained unchallenged for nearly 30 years. Our other algorithm, which is more practical, runs in $O(n \log n + p^2 \log^2(n/p))$ time, and when $p=O(\sqrt{n})$ it is faster than Megiddo and Tamir's $O(n \log^2n \log\log n)$ time algorithm [megiddo1983].

preprint2015arXiv

Almost Empty Monochromatic Triangles in Planar Point Sets

For positive integers $c, s \geq 1$ , let $M_3(c, s)$ be the least integer such that any set of at least $M_3(c, s)$ points in the plane, no three on a line and colored with $c$ colors, contains a monochromatic triangle with at most $s$ interior points. The case $s=0$ , which corresponds to empty monochromatic triangles, has been studied extensively over the last few years. In particular, it is known that $M_3(1, 0)=3$ , $M_3(2, 0)=9$ and $M_3(c, 0)=\infty$ , for $c\geq 3$ . In this paper we extend these results when $c \geq 2$ and $s \geq 1$ . We prove that the least integer $λ_3(c)$ such that $M_3(c, λ_3(c))< \infty$ satisfies: $\left\lfloor\frac{c-1}{2}\right\rfloor \leqλ_3(c)\leq c-2,$ where $c \geq 2$ . Moreover, the exact values of $M_3(c, s)$ are determined for small values of $c$ and $s$ . We also conjecture that $λ_3(4)=1$ , and verify it for sufficiently large Horton sets.

preprint2015arXiv

On chromatic number of colored mixed graphs

An $(m,n)$ -colored mixed graph $G$ is a graph with its arcs having one of the $m$ different colors and edges having one of the $n$ different colors. A homomorphism $f$ of an $(m,n)$ -colored mixed graph $G$ to an $(m,n)$ -colored mixed graph $H$ is a vertex mapping such that if $uv$ is an arc (edge) of color $c$ in $G$ , then $f(u)f(v)$ is an arc (edge) of color $c$ in $H$ . The \textit{ $(m,n)$ -colored mixed chromatic number} $χ_{(m,n)}(G)$ of an $(m,n)$ -colored mixed graph $G$ is the order (number of vertices) of the smallest homomorphic image of $G$ . This notion was introduced by Nešetřil and Raspaud (2000, J. Combin. Theory, Ser. B 80, 147--155). They showed that $χ_{(m,n)}(G) \leq k(2m+n)^{k-1}$ where $G$ is a $k$ -acyclic colorable graph. We proved the tightness of this bound. We also showed that the acyclic chromatic number of a graph is bounded by $k^2 + k^{2 + \lceil log_{(2m+n)} log_{(2m+n)} k \rceil}$ if its $(m,n)$ -colored mixed chromatic number is at most $k$ . Furthermore, using probabilistic method, we showed that for graphs with maximum degree $Δ$ its $(m,n)$ -colored mixed chromatic number is at most $2(Δ-1)^{2m+n} (2m+n)^{Δ-1}$ . In particular, the last result directly improves the upper bound $2Δ^2 2^Δ$ of oriented chromatic number of graphs with maximum degree $Δ$ , obtained by Kostochka, Sopena and Zhu (1997, J. Graph Theory 24, 331--340) to $2(Δ-1)^2 2^{Δ-1}$ . We also show that there exists a graph with maximum degree $Δ$ and $(m,n)$ -colored mixed chromatic number at least $(2m+n)^{Δ/ 2}$ .

preprint2014arXiv

Voronoi Game on Graphs

\textit{Voronoi game} is a geometric model of competitive facility location problem played between two players. Users are generally modeled as points uniformly distributed on a given underlying space. Each player chooses a set of points in the underlying space to place their facilities. Each user avails service from its nearest facility. Service zone of a facility consists of the set of users which are closer to it than any other facility. Payoff of each player is defined by the quantity of users served by all of its facilities. The objective of each player is to maximize their respective payoff. In this paper we consider the two players {\it Voronoi game} where the underlying space is a road network modeled by a graph. In this framework we consider the problem of finding $k$ optimal facility locations of Player 2 given any placement of $m$ facilities by Player 1. Our main result is a dynamic programming based polynomial time algorithm for this problem on tree network. On the other hand, we show that the problem is strongly $\mathcal{NP}$ -complete for graphs. This proves that finding a winning strategy of P2 is $\mathcal{NP}$ -complete. Consequently, we design an $1-\frac{1}{e}$ factor approximation algorithm, where $e \approx 2.718$ .

preprint2013arXiv

On Pseudo-Convex Partitions of a Planar Point Set

Aichholzer et al. [{\it Graphs and Combinatorics}, Vol. 23, 481-507, 2007] introduced the notion of pseudo-convex partitioning of planar point sets and proved that the pseudo-convex partition number $ψ(n)$ satisfies, $\frac{3}{4}\lfloor\frac{n}{4}\rfloor\leq ψ(n)\leq\lceil\frac{n}{4}\rceil$ . In this paper we prove that $ψ(13)=3$ , which immediately improves the upper bound on $ψ(n)$ to $\lceil\frac{3n}{13}\rceil$ , thus answering a question posed by Aichholzer et al. in the same paper.

preprint2012arXiv

Holes or Empty Pseudo-Triangles in Planar Point Sets

Let $E(k, \ell)$ denote the smallest integer such that any set of at least $E(k, \ell)$ points in the plane, no three on a line, contains either an empty convex polygon with $k$ vertices or an empty pseudo-triangle with $\ell$ vertices. The existence of $E(k, \ell)$ for positive integers $k, \ell\geq 3$ , is the consequence of a result proved by Valtr [Discrete and Computational Geometry, Vol. 37, 565--576, 2007]. In this paper, following a series of new results about the existence of empty pseudo-triangles in point sets with triangular convex hulls, we determine the exact values of $E(k, 5)$ and $E(5, \ell)$ , and prove bounds on $E(k, 6)$ and $E(6, \ell)$ , for $k, \ell\geq 3$ . By dropping the emptiness condition, we define another related quantity $F(k, \ell)$ , which is the smallest integer such that any set of at least $F(k, \ell)$ points in the plane, no three on a line, contains a convex polygon with $k$ vertices or a pseudo-triangle with $\ell$ vertices. Extending a result of Bisztriczky and Tóth [Discrete Geometry, Marcel Dekker, 49--58, 2003], we obtain the exact values of $F(k, 5)$ and $F(k, 6)$ , and obtain non-trivial bounds on $F(k, 7)$ .

preprint2012arXiv

Localized Geometric Query Problems

A new class of geometric query problems are studied in this paper. We are required to preprocess a set of geometric objects $P$ in the plane, so that for any arbitrary query point $q$ , the largest circle that contains $q$ but does not contain any member of $P$ , can be reported efficiently. The geometric sets that we consider are point sets and boundaries of simple polygons.

preprint2010arXiv

Querying for the Largest Empty Geometric Object in a Desired Location

We study new types of geometric query problems defined as follows: given a geometric set $P$ , preprocess it such that given a query point $q$ , the location of the largest circle that does not contain any member of $P$ , but contains $q$ can be reported efficiently. The geometric sets we consider for $P$ are boundaries of convex and simple polygons, and point sets. While we primarily focus on circles as the desired shape, we also briefly discuss empty rectangles in the context of point sets.

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.

Sandip Das

Research overview

Is this your work?

20 publications

On clique numbers of colored mixed graphs

Schedulers Synchronization Supporting Ultra Reliable Low Latency Communications (URLLC) in Cloud-RAN over Virtualised Mesh PON

Frequency power spectra of global quantities in magnetoconvection

Pseudoline arrangement graphs: degree sequences and eccentricities

Algorithms and complexity for geodetic sets on planar and chordal graphs

PON Virtualisation with EAST-WEST Communications for Low-Latency Converged Multi-Access Edge Computing (MEC)

Thermal flux in unsteady Rayleigh-Bénard magnetoconvection

Chromatic number of signed graphs with bounded maximum degree

Geometric k-Center Problems with Centers Constrained to Two Lines

Linear-Time Fitting of a $k$ -Step Function

On a special class of boxicity 2 graphs

On local structures of cubicity 2 graphs

The $p$ -Center Problem in Tree Networks Revisited

Almost Empty Monochromatic Triangles in Planar Point Sets

On chromatic number of colored mixed graphs

Voronoi Game on Graphs

On Pseudo-Convex Partitions of a Planar Point Set

Holes or Empty Pseudo-Triangles in Planar Point Sets

Localized Geometric Query Problems

Querying for the Largest Empty Geometric Object in a Desired Location

See the researcher in context

Building this map preview

Sandip Das

Research overview

Is this your work?

20 publications

On clique numbers of colored mixed graphs

Schedulers Synchronization Supporting Ultra Reliable Low Latency Communications (URLLC) in Cloud-RAN over Virtualised Mesh PON

Frequency power spectra of global quantities in magnetoconvection

Pseudoline arrangement graphs: degree sequences and eccentricities

Algorithms and complexity for geodetic sets on planar and chordal graphs

PON Virtualisation with EAST-WEST Communications for Low-Latency Converged Multi-Access Edge Computing (MEC)

Thermal flux in unsteady Rayleigh-Bénard magnetoconvection

Chromatic number of signed graphs with bounded maximum degree

Geometric k-Center Problems with Centers Constrained to Two Lines

Linear-Time Fitting of a kkk-Step Function

On a special class of boxicity 2 graphs

On local structures of cubicity 2 graphs

The ppp-Center Problem in Tree Networks Revisited

Almost Empty Monochromatic Triangles in Planar Point Sets

On chromatic number of colored mixed graphs

Voronoi Game on Graphs

On Pseudo-Convex Partitions of a Planar Point Set

Holes or Empty Pseudo-Triangles in Planar Point Sets

Localized Geometric Query Problems

Querying for the Largest Empty Geometric Object in a Desired Location

See the researcher in context

Building this map preview

Linear-Time Fitting of a $k$ -Step Function

The $p$ -Center Problem in Tree Networks Revisited