BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Subhabrata Paul

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

ResearcherUnclaimed source record
Discrete MathematicsInformation Theorymath.COmath.ITComputational ComplexityComputational GeometryData Structures and Algorithms

Catalog footprint

Research overview

6works
7topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

6 publications

preprint2022arXiv

A Direct Construction of Cross Z-Complementary Sequence Sets with Large Set Size

This letter presents a direct construction of cross Z-complementary sequence sets (CZCSSs), whose aperiodic correlation sums exhibit zero correlation zones at both the front-end and tail-end shifts. CZCSS can be regarded as an extension of the symmetrical Z-complementary code set (SZCCS). The available construction of SZCCS has a limitation on the set size, with a maximum set size of 8. The proposed generalized Boolean function based construction can generate CZCSS of length in the form of non-power-of-two with variable set size 2n+12^{n+1}, where each code has 2n+12^{n+1} constituent sequences. The proposed construction also yields cross Z-complementary pairs and cross Z-complementary sets with a large number of constituent sequences compared to the existing work.

Open access
preprint2022arXiv

A Direct Construction of GCP and Binary CCC of Length Non Power of Two

Golay complementary pairs (GCPs) and complete complementary codes (CCCs) have found a wide range of practical applications in coding, signal processing and wireless communication due to their ideal correlation properties. In fact, binary CCCs have special advantages in spread spectrum communication due to their simple modulo-2 arithmetic operation, modulation and correlation simplicity, but they are limited in length. In this paper, we present a direct construction of GCPs, mutually orthogonal complementary sets (MOCSs) and binary CCCs of non-power of two lengths to widen their application in the recent field. First, a generalised Boolean function (GBF) based truncation technique has been used to construct GCPs of non-power of two lengths. Then Complementary sets (CSs) and MOCSs of lengths of the form 2m−1+2m−32^{m-1}+2^{m-3} (m≥5m \geq 5) and 2m−1+2m−2+2m−42^{m-1}+2^{m-2}+2^{m-4} (m≥6m \geq 6) are generated by GBFs. Finally, binary CCCs with desired lengths are constructed using the union of MOCSs. The row and column sequence peak to mean envelope power ratio (PMEPR) has been investigated and compared with existing work. The column sequence PMEPR of resultant CCCs can be effectively upper bounded by 22.

Open access
preprint2022arXiv

Transitivity on subclasses of bipartite graphs

Let G=(V,E)G=(V, E) be a graph where VV and EE are the vertex and edge set, respectively. For two disjoint subsets AA and BB, we say AA dominates BB if every vertex of BB is adjacent to at least one vertex of AA. A vertex partition π={V1,V2,…,Vk}π= \{V_1, V_2, \ldots, V_k\} of GG is called a \emph{transitive kk-partition} if ViV_i dominates VjV_j for all i,ji,j where 1≤i<j≤k1\leq i<j\leq k. The maximum integer kk for which the above partition exists is called \emph{transitivity} of GG and it is denoted by Tr(G)Tr(G). The \textsc{Maximum Transitivity Problem} is to find a transitive partition of a given graph with the maximum number of partitions. It was known that the decision version of \textsc{Maximum Transitivity Problem} is NP-complete for general graphs, which was proved by Hedetniemi et al. [Iterated colorings of graphs, \emph{Discrete Mathematics}, 278, 2004]. This paper first strengthens the NP-completeness result by showing that this problem remains NP-complete for perfect elimination bipartite graphs. On the other hand, we propose a linear-time algorithm for finding the transitivity of a given bipartite chain graph. We then characterize graphs with transitivity at least tt for any integer tt. This result answers two open questions posed by J. T. Hedetniemi and S. T. Hedetniemi [The transitivity of a graph, \emph{J. Combin. Math. Combin. Comput}, 104, 2018].

Open access
preprint2015arXiv

Uniformity of point samples in metric spaces using gap ratio

Teramoto et al. defined a new measure called the gap ratio that measures the uniformity of a finite point set sampled from S\cal S, a bounded subset of R2\mathbb{R}^2. We generalize this definition of measure over all metric spaces by appealing to covering and packing radius. The definition of gap ratio needs only a metric unlike discrepancy, a widely used uniformity measure, that depends on the notion of a range space and its volume. We also show some interesting connections of gap ratio to Delaunay triangulation and discrepancy in the Euclidean plane. The major focus of this work is on solving optimization related questions about selecting uniform point samples from metric spaces; the uniformity being measured using gap ratio. We consider discrete spaces like graph and set of points in the Euclidean space and continuous spaces like the unit square and path connected spaces. We deduce lower bounds, prove hardness and approximation hardness results. We show that a general approximation algorithm framework gives different approximation ratios for different metric spaces based on the lower bound we deduce. Apart from the above, we show existence of coresets for sampling uniform points from the Euclidean space -- for both the static and the streaming case. This leads to a (1+ε)\left( 1+ε\right)-approximation algorithm for uniform sampling from the Euclidean space.

Open access
preprint2014arXiv

(1,j)(1,j)-set problem in graphs

A subset D⊆VD \subseteq V of a graph G=(V,E)G = (V, E) is a (1,j)(1, j)-set if every vertex v∈V∖Dv \in V \setminus D is adjacent to at least 11 but not more than jj vertices in D. The cardinality of a minimum (1,j)(1, j)-set of GG, denoted as γ(1,j)(G)γ_{(1,j)} (G), is called the (1,j)(1, j)-domination number of GG. Given a graph G=(V,E)G = (V, E) and an integer kk, the decision version of the (1,j)(1, j)-set problem is to decide whether GG has a (1,j)(1, j)-set of cardinality at most kk. In this paper, we first obtain an upper bound on γ(1,j)(G)γ_{(1,j)} (G) using probabilistic methods, for bounded minimum and maximum degree graphs. Our bound is constructive, by the randomized algorithm of Moser and Tardos [MT10], We also show that the (1,j)(1, j)- set problem is NP-complete for chordal graphs. Finally, we design two algorithms for finding γ(1,j)(G)γ_{(1,j)} (G) of a tree and a split graph, for any fixed jj, which answers an open question posed in [CHHM13].

Open access
preprint2014arXiv

Linear kernels for k-tuple and liar's domination in bounded genus graphs

A set D⊆VD\subseteq V is called a kk-tuple dominating set of a graph G=(V,E)G=(V,E) if ∣NG[v]∩D∣≥k\left| N_G[v] \cap D \right| \geq k for all v∈Vv \in V, where NG[v]N_G[v] denotes the closed neighborhood of vv. A set D⊆VD \subseteq V is called a liar's dominating set of a graph G=(V,E)G=(V,E) if (i) ∣NG[v]∩D∣≥2\left| N_G[v] \cap D \right| \geq 2 for all v∈Vv\in V and (ii) for every pair of distinct vertices u,v∈Vu, v\in V, ∣(NG[u]∪NG[v])∩D∣≥3\left| (N_G[u] \cup N_G[v]) \cap D \right| \geq 3. Given a graph GG, the decision versions of kk-Tuple Domination Problem and the Liar's Domination Problem are to check whether there exists a kk-tuple dominating set and a liar's dominating set of GG of a given cardinality, respectively. These two problems are known to be NP-complete \cite{LiaoChang2003, Slater2009}. In this paper, we study the parameterized complexity of these problems. We show that the kk-Tuple Domination Problem and the Liar's Domination Problem are W[2]\mathsf{W}[2]-hard for general graphs but they admit linear kernels for graphs with bounded genus.

Open access

Research graph

See the researcher in context

Open full explorer

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.