Author

Author

Sort by: Order: Results:

  • Das, Bireswar; Scharpfenecker, Patrick; Toran, Jacobo (Elsevier, 2017-04)
    It is well-known that succinct encodings of computational problems – using circuits or formulas to encode large instances – generally result in an exponential complexity blow-up compared to their original complexity. We ...
  • Arvind, V.; Das, Bireswar; Köbler, Johannes; Seinosuke, Toda (2010)
    We describe a xed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism which has running time 2 O (b)NO(1), where the parameter is the maximum size of the color classes of the given hypergraphs and N ...
  • Arvind, V.; Das, Bireswar; Kobler, Johannes; Toda, Seinosuke (Springer, 2015-01)
    We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism, denoted CHI, which has running time (2 b N) O(1), where the parameter b is the maximum size of the color classes of the given ...
  • Das, Bireswar; Pal, Manjish; Visavaliya, Vijay (arXiv, Cornell University Library, 2011-10)
    In this paper, we prove that most of the boolean functions, f : {−1, 1} n → {−1, 1}satisfy the Fourier Entropy Influence (FEI) Conjecture due to Friedgut and Kalai(Proc. AMS’96)[1]. The conjecture says that the Entropy of ...
  • Arvind, V.; Das, Bireswar; Köbler, Johannes; Kuhnert, Sebastian (Elsevier, 2012-08)
    We show that, for k constant, k -tree isomorphism can be decided in logarithmic space by giving an View the MathML sourceO(klogn) space canonical labeling algorithm. The algorithm computes a unique tree decomposition, ...
  • Das, Bireswar; Datta, Samir; Prajakta, Nimbhorkar (Springer Link, 2013-05)
    Reachability and shortest path problems are NL-complete for general graphs. They are known to be in L for graphs of tree-width 2 (Jakoby and Tantau in Proceedings of FSTTCS’07: The 27th Annual Conference on Foundations of ...
  • Das, Bireswar; Enduri, Murali Krishna; Reddy, I. Vinod (Springer, 2015-02)
    We give a deterministic logspace algorithm for the graph isomorphism problem for graphs with bounded tree-depth. We also show that the graph isomorphism problem is fixed parameter tractable for a related parameterized graph ...
  • Das, Bireswar; Sharma, Shivdutt (2019-07-01)
  • Das, Bireswar; Sharma, Shivdutt (Springer, 2020-10)
    The isomorphism problem for groups, when the groups are given by their Cayley tables is a well-studied problem. This problem has been studied for various restricted classes of groups. Kavitha gave a linear time isomorphism ...
  • Das, Bireswar; Dasgupta, Anirban; Enduri, Murali Krishna; Reddy, Vinod.I (Elsevier, 2018-11)
    In this paper, we show that for a fixed k, there is an NC algorithm that separates the graphs of rank-width at most k from those with rank-width at least
  • Das, Bireswar; Enduri, Murali Krishna; Misra, Neeldhara; Reddy, I. Vinod (Cornell University Library, 2017-11)
    The Firefighting problem is defined as follows. At time t=0, a fire breaks out at a vertex of a graph. At each time step t?0, a firefighter permanently defends (protects) an unburned vertex, and the fire then spread to all ...
  • Das, Bireswar; Enduri, Murali Krishna; Misra, Neeldhara; Reddy, I. Vinod (Springer, 2018-02-15)
    The Firefighting problem is defined as follows. At time Open image in new window , a fire breaks out at a vertex of a graph. At each time step Open image in new window , a firefighter permanently defends (protects) an ...
  • Das, Bireswar; Enduri, Murali Krishna; Kiyomi, Masashi; Misra, Neeldhara; Otachi, Yota; Reddy, I. Vinod; Yoshimura, Shunya (Elsevier, 2019-03)
    he Firefighting problem is defined as follows. At time , a fire breaks out at a vertex of a graph. At each time step, a firefighter permanently defends (protects) an unburned vertex, and the fire then spreads to all ...
  • Das, Bireswar; Enduri, Murali Krishna; Misra, Neeldhara; Vinod Reddy, I. (Springer International Publishing, 2017)
    Structural parameterizations for hard problems have proven to be a promising venture for discovering scenarios where the problem is tractable. In particular, when a problem is already known to be polynomially solvable for ...
  • Das, Bireswar; Enduri, Murali Krishna; Reddy, I. Vinod (2018-03-03)
  • Das, Bireswar; Enduri, Murali Krishna; Reddy, I. Vinod (Cornell University Library, 2017-12)
    In this paper, we study the parallel and the space complexity of the graph isomorphism problem (\GI{}) for several parameterizations. Let H={H1,H2,?,Hl} be a finite set of graphs where |V(Hi)|?d for all i and for some ...
  • Das, Bireswar; Enduri, Murali Krishna; Reddy, I. Vinod (Cornell University Library, 2015-06)
    The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. While there are many results on the ...
  • Das, Bireswar; Enduri, Murali Krishna; Reddy, I. Vinod (Springer, 2016-07)
    The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. We give a polynomial time graph isomorphism ...
  • Das, Bireswar; Enduri, Murali Krishna; Reddy, I. Vinod (Elsevier, 2020-06)
    The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. We give a polynomial time graph isomorphism ...
  • Das, Bireswar; Toran, Jacobo; Wagner, Fabian (Elsevier, 2012-08)
    The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time. We give restricted space algorithms for these problems proving the following ...

Search Digital Repository


Browse

My Account