Výsledky vyhledávání - "Bireswar Das"

Space efficient representations of finite groups

Autor: Bireswar Das, P. R. Vaidyanathan, Shivdutt Sharma

Publikováno v: Journal of Computer and System Sciences. 114:137-146

The Cayley table representation of a group uses O ( n 2 ) words for a group of order n and answers multiplication queries in time O ( 1 ) . It is interesting to ask if there is a o ( n 2 ) space representation of groups that still has O ( 1 ) query-t

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a72ae116b3eb2cbbf2949541c6a4895a
https://doi.org/10.1016/j.jcss.2020.06.007

Zobrazit plný text záznamu

Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes

Autor: Bireswar Das, Shivdutt Sharma

Publikováno v: Theory of Computing Systems. 65:497-514

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 algorithm for abelian group

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b70d918acd9610f3faab0853d49ef0cd
https://doi.org/10.1007/s00224-020-10010-z

Zobrazit plný text záznamu

Compact Data Structures for Dedekind Groups and Finite Rings

Autor: Bireswar Das, Shivdutt Sharma

Publikováno v: WALCOM: Algorithms and Computation ISBN: 9783030682101
WALCOM

A group with n elements can be stored using \(\mathcal {O}(n^2)\) space via its Cayley table which can answer a group multiplication query in \(\mathcal {O}(1)\) time. Information theoretically it needs \(\varOmega (n\log n)\) bits or \(\varOmega (n)

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::bfba9001e83c9f82145582cda25753e0
https://doi.org/10.1007/978-3-030-68211-8_8

Zobrazit plný text záznamu

On NC algorithms for problems on bounded rank-width graphs

Autor: Bireswar Das, Anirban Dasgupta, I. Vinod Reddy, Murali Krishna Enduri

Publikováno v: Information Processing Letters. 139:64-67

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
by Bireswar Das, Anirban Dasgupta, Murali Krishna Enduri, and Vinod I. Reddy
2018-08-1

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ffdd3c73f60277bd19055a87dd4d56f6
https://doi.org/10.1016/j.ipl.2018.07.007

Zobrazit plný text záznamu

On structural parameterizations of firefighting

Autor: Bireswar Das, Murali Krishna Enduri, Masashi Kiyomi, Neeldhara Misra, Yota Otachi, I. Vinod Reddy, Shunya Yoshimura

Publikováno v: CALDAM

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 undefended neighbors from the vert

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0d8aaf1f556874684a3b84f30003ccc9
https://repository.iitgn.ac.in/handle/123456789/4289

Zobrazit plný text záznamu

Succinct Representations of Finite Groups

Autor: Bireswar Das, P. R. Vaidyanathan, Shivdutt Sharma

Publikováno v: Fundamentals of Computation Theory ISBN: 9783030250263
FCT

The Cayley table representation of a group uses \(O(n^2)\) words for a group of order n and answers multiplication queries in time O(1) in word RAM model. It is interesting to ask if there is a \(o(n^2)\) space representation of groups that still has

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::a892dbec6190151cb74de2791181a6e4
https://doi.org/10.1007/978-3-030-25027-0_16

Zobrazit plný text záznamu

Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes

Autor: Bireswar Das, Shivdutt Sharma

Publikováno v: Computer Science – Theory and Applications ISBN: 9783030199548
CSR

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::4d0641b3c91e9ab76f6dc79cdb8d828a
https://doi.org/10.1007/978-3-030-19955-5_8

Zobrazit plný text záznamu

On Structural Parameterizations of Firefighting

Autor: Bireswar Das, Murali Krishna Enduri, Neeldhara Misra, I. Vinod Reddy

Publikováno v: Algorithms and Discrete Applied Mathematics ISBN: 9783319741796

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::6d81b9bb3be22d4d86e5c8701bef2b37
https://doi.org/10.1007/978-3-319-74180-2_19

Zobrazit plný text záznamu

On the Parallel Parameterized Complexity of the Graph Isomorphism Problem

Autor: Bireswar Das, Murali Krishna Enduri, I. Vinod Reddy

Publikováno v: WALCOM: Algorithms and Computation ISBN: 9783319751719
WALCOM

In this paper, we study the parallel and the space complexity of the graph isomorphism problem (\(\mathsf {GI}\)) for several parameterizations.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::d26ab0ddff7bfcdd85c83a9e4f67eb73
https://doi.org/10.1007/978-3-319-75172-6_22

Zobrazit plný text záznamu

On Structural Parameterizations of Graph Motif and Chromatic Number

Autor: Bireswar Das, Murali Krishna Enduri, Neeldhara Misra, I. Vinod Reddy

Publikováno v: Algorithms and Discrete Applied Mathematics ISBN: 9783319530062
CALDAM

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 some class of inputs, then i

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::28162f699c57eb0d4faa4f2ab020800a
https://doi.org/10.1007/978-3-319-53007-9_11

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání