Zobrazeno 1 - 8
of 8
pro vyhledávání: '"Sharma, Vimal Raj"'
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
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, that for directed planar graphs, the problem can be solved in polynomia
Externí odkaz:
http://arxiv.org/abs/2407.00237
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:
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 [Samir Datta et al., 2018; Samir Datta et al., 2018; Samir Datta et al., 2020]. Re
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d1204a3c34d843e8b87d8ddea523d439
We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists. As a consequence, w
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::93336a66222c92364b55e5f6d3342c0d
The catalytic Turing machine is a model of computation defined by Buhrman, Cleve, Koucký, Loff, and Speelman (STOC 2014). Compared to the classical space-bounded Turing machine, this model has an extra space which is filled with arbitrary content in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d8ffe453b96596b69afc937fab9d96e1
We show that given an embedding of an O(log n) genus graph G and two vertices s and t in G, deciding if there is a path from s to t in G is in unambiguous logarithmic space. Unambiguous computation is a restriction of nondeterministic computation whe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e9700a9c31518c7bc55839fe975e9320