Zobrazeno 1 - 10
of 52
pro vyhledávání: '"Tewari, Raghunath"'
Autor:
Bhadra, Ronak, Tewari, Raghunath
Deciding if there exists a path from one vertex to another in a graph is known as the s-t connectivity or the reachability problem. Reachability can be solved using graph traversal algorithms like Depth First Search(DFS) or Breadth First Search(BFS)
Externí odkaz:
http://arxiv.org/abs/2409.18469
A catalytic Turing machine is a variant of a Turing machine in which there exists an auxiliary tape in addition to the input tape and the work tape. This auxiliary tape is initially filled with arbitrary content. The machine can read and write on the
Externí odkaz:
http://arxiv.org/abs/2408.14670
Autor:
Datta, Samir, Gupta, Chetan, Jain, Rahul, Mukherjee, Anish, Sharma, Vimal Raj, Tewari, Raghunath
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, DMVZ18, DKMTVZ20]. Reachability can be maintained with first-order updat
Externí odkaz:
http://arxiv.org/abs/2109.01875
Autor:
Datta, Samir, Gupta, Chetan, Jain, Rahul, Mukherjee, Anish, Sharma, Vimal Raj, Tewari, Raghunath
We show that for each single crossing graph $H$, a polynomially bounded weight function for all $H$-minor free graphs $G$ can be constructed in Logspace such that it gives nonzero weights to all the cycles in $G$. This class of graphs subsumes almost
Externí odkaz:
http://arxiv.org/abs/2103.13940
Autor:
Jain, Rahul, Tewari, Raghunath
Publikováno v:
In Theoretical Computer Science 8 January 2024 982
A graph separator is a subset of vertices of a graph whose removal divides the graph into small components. Computing small graph separators for various classes of graphs is an important computational task. In this paper, we present a polynomial time
Externí odkaz:
http://arxiv.org/abs/2005.06419
The authors have withdrawn this paper due to an error in the proof of Lemma 3.4. -------------------------------------------------------------------------------------------- The authors have withdrawn this paper due to an error in the proof of Lemma
Externí odkaz:
http://arxiv.org/abs/2002.12856
Autor:
Jain, Rahul, Tewari, Raghunath
The reachability problem is to determine if there exists a path from one vertex to another in a graph. Grid graphs are the class of graphs where vertices are present on the lattice points of a two-dimensional grid, and an edge can occur between a ver
Externí odkaz:
http://arxiv.org/abs/1902.00488
Autor:
Jain, Rahul, Tewari, Raghunath
Reachability is the problem of deciding whether there is a path from one vertex to the other in the graph. Standard graph traversal algorithms such as DFS and BFS take linear time to decide reachability however their space complexity is also linear.
Externí odkaz:
http://arxiv.org/abs/1901.11285
Autor:
Ojha, Aayush, Tewari, Raghunath
Recently, perfect matching in bounded planar cutwidth bipartite graphs (\BGGM) was shown to be in ACC$^0$ by Hansen et al.. They also conjectured that the problem is in AC$^0$. In this paper, we disprove their conjecture by showing that the problem i
Externí odkaz:
http://arxiv.org/abs/1801.00906