Pawan Aurora

collaborators

2 papers

cs.DS2013

Completely Positive formulation of the Graph Isomorphism Problem

Shashank K Mehta, Pawan Aurora

Given two graphs $G_{1}$ and $G_{2}$ on $n$ vertices each, we define a graph $G$ on vertex set $V_{1} \times V_{2}$ and the edge set as the union of edges of $G_{1} \times G_{2} ˉ$ , $\bar{G_…

cs.DS2012

Partial Degree Bounded Edge Packing Problem with Arbitrary Bounds

Pawan Aurora, Sumit Singh, Shashank K. Mehta

We study the Partial Degree Bounded Edge Packing (PDBEP) problem introduced in [5] by Zhang. They have shown that this problem is NP-Hard even for uniform degree constraint. They a…