Source author record

Pratik Ghosal

Pratik Ghosal appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computer Science and Game Theory gr-qc hep-th

Catalog footprint

What is connected

3works

4topics

3close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2022arXiv

Probability distribution for black hole evaporation

Non-thermal correction to the emission probability of particles from black holes can be obtained if the backreaction or self-gravitational effects of the emitted particles on the black hole spacetime are taken into consideration. These non-thermally emitted particles conserve the entropy of the black hole, i.e, the entropy of the system of radiated particles after complete evaporation of the black hole matches the initial entropy of the black hole. Using the non-thermal emission probability, we have determined the probability for a black hole of mass $M$ to be completely evaporated by a given number of particles $n$. This is done by first evaluating the number of possible ways in which the black hole can be evaporated by emitting $n$ number of particles, and then the total number of ways in which the black hole can be evaporated. The ratio of these two quantities gives us the desired probability. From the probability distribution, we get a displacement relation between the most probable number of particles exhausting the black hole and the temperature of the initial black hole. This relation resembles Wien's displacement law for blackbody radiation.

preprint2020arXiv

The Dynamics of Rank-Maximal and Popular Matchings

Given a bipartite graph, where the two sets of vertices are applicants and posts and ranks on the edges represent preferences of applicants over posts, a {\em rank-maximal} matching is one in which the maximum number of applicants is matched to their rank one posts and subject to this condition, the maximum number of applicants is matched to their rank two posts, and so on. We study the dynamic version of the problem in which a new applicant or post may be added to the graph and we would like to maintain a rank-maximal matching. We show that after the arrival of one vertex, we are always able to update the existing rank-maximal matching in $\mathcal{O}(\min(c'n ,n^2) + m)$ time, where $n$ denotes the number of applicants, $m$ the number of edges and $c'$ the maximum rank of an edge in an optimal solution. Additionally, we update the matching using a minimal number of changes (replacements). All cases of a deletion of a vertex/edge and an addition of an edge can be reduced to the problem of handling the addition of a vertex. As a by-product, we also get an analogous $\mathcal{O}(m)$ result for the dynamic version of the (one-sided) popular matching problem. Our results are based on the novel use of the properties of the Edmonds-Gallai decomposition. The presented ideas may find applications in other (dynamic) matching problems.

preprint2015arXiv

Characterisation of Strongly Stable Matchings

An instance of a strongly stable matching problem (SSMP) is an undirected bipartite graph $G=(A \cup B, E)$, with an adjacency list of each vertex being a linearly ordered list of ties, which are subsets of vertices equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching $M$ is a set of vertex-disjoint edges. An edge $(x,y) \in E \setminus M$ is a {\em blocking edge} for $M$ if $x$ is either unmatched or strictly prefers $y$ to its current partner in $M$, and $y$ is either unmatched or strictly prefers $x$ to its current partner in $M$ or is indifferent between them. A matching is {\em strongly stable} if there is no blocking edge with respect to it. We present an algorithm for the generation of all strongly stable matchings, thus solving an open problem already stated in the book by Gusfield and Irving \cite{GI}. It has previously been shown that strongly stable matchings form a distributive lattice and although the number of strongly stable matchings can be exponential in the number of vertices, we show that there exists a partial order with $O(m)$ elements representing all strongly stable matchings, where $m$ denotes the number of edges in the graph. We give two algorithms that construct two such representations: one in $O(nm^2)$ time and the other in $O(nm)$ time, where $n$ denotes the number of vertices in the graph. Note that the construction of the second representation has the same time complexity as that of computing a single strongly stable matching.