4 citations · 13 across the 12 of their papers we have counts for
3 papers · 1 filter
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…
3-connected Planar Graph Isomorphism is in Log-space
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar
We show that the isomorphism of 3-connected planar graphs can be decided in deterministic log-space. This improves the previously known bound ULcoUL of Thierauf and Wagner.
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs
Samir Datta, Raghav Kulkarni, Sambuddha Roy
We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolati…