2 citations · 2 across the 1 of their papers we have counts for
2 papers
cs.CC2008★ 2 cited
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.
cs.DS2008
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…