Publications (34)
The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs
Archit Chauhan, Samir Datta, Chetan Gupta +1
Finding a simple path of even length between two designated vertices in a directed graph is a fundamental NP-complete problem known as the EvenPath problem. Nedev proved in 1999, t…
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…
Dynamic Meta-theorems for Distance and Matching
Samir Datta, Chetan Gupta, Rahul Jain +3
Reachability, distance, and matching are some of the most fundamental graph problems that have been of particular interest in dynamic complexity theory in recent years [DKMSZ18, DM…
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…
A Log-space Algorithm for Canonization of Planar Graphs
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar +2
Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. We bridge this gap for a n…
Reachability and Matching in Single Crossing Minor Free Graphs
Samir Datta, Chetan Gupta, Rahul Jain +3
We show that for each single crossing graph , a polynomially bounded weight function for all -minor free graphs can be constructed in Logspace such that it gives nonzero…