3 papers
cs.CC2026
Maximum Matching and Related Problems in Catalytic Logspace
Srijan Chakraborty, Samir Datta, Aryan Kusre +2
Understanding the power of space-bounded computation with access to catalytic space has been an important theme in complexity theory over the recent years. One of the key algorithm…
cs.DS2025
Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
Archit Chauhan, Samir Datta, M. Praveen
Constructing a Depth First Search (DFS) tree is a fundamental graph problem, whose parallel complexity is still not settled. Reif showed parallel intractability of lex-first DFS. I…
cs.DS2025
A parallel algorithm for the odd two-face shortest k-disjoint path problem
Srijan Chakraborty, Samir Datta
The shortest Disjoint Path problem (SDPP) requires us to find pairwise vertex disjoint paths between k designated pairs of terminal vertices such that the sum of the path lengths i…