Pushdown reachability with constant treewidth

K. Chatterjee, G.F. Osang, Information Processing Letters 122 (2017) 25–29.

Download
OA 247.66 KB

Journal Article | Published | English
Abstract
We consider the problem of reachability in pushdown graphs. We study the problem for pushdown graphs with constant treewidth. Even for pushdown graphs with treewidth 1, for the reachability problem we establish the following: (i) the problem is PTIME-complete, and (ii) any subcubic algorithm for the problem would contradict the k-clique conjecture and imply faster combinatorial algorithms for cliques in graphs.
Publishing Year
Date Published
2017-06-01
Journal Title
Information Processing Letters
Volume
122
Page
25 - 29
ISSN
IST-REx-ID

Cite this

Chatterjee K, Osang GF. Pushdown reachability with constant treewidth. Information Processing Letters. 2017;122:25-29. doi:10.1016/j.ipl.2017.02.003
Chatterjee, K., & Osang, G. F. (2017). Pushdown reachability with constant treewidth. Information Processing Letters, 122, 25–29. https://doi.org/10.1016/j.ipl.2017.02.003
Chatterjee, Krishnendu, and Georg F Osang. “Pushdown Reachability with Constant Treewidth.” Information Processing Letters 122 (2017): 25–29. https://doi.org/10.1016/j.ipl.2017.02.003.
K. Chatterjee and G. F. Osang, “Pushdown reachability with constant treewidth,” Information Processing Letters, vol. 122, pp. 25–29, 2017.
Chatterjee K, Osang GF. 2017. Pushdown reachability with constant treewidth. Information Processing Letters. 122, 25–29.
Chatterjee, Krishnendu, and Georg F. Osang. “Pushdown Reachability with Constant Treewidth.” Information Processing Letters, vol. 122, Elsevier, 2017, pp. 25–29, doi:10.1016/j.ipl.2017.02.003.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2019-10-15T07:44:51Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar