Pushdown reachability with constant treewidth
Chatterjee K, Osang GF. 2017. Pushdown reachability with constant treewidth. Information Processing Letters. 122, 25–29.
Download
Journal Article
| Published
| English
Scopus indexed
Department
Grant
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
Publisher
Elsevier
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. Elsevier. https://doi.org/10.1016/j.ipl.2017.02.003
Chatterjee, Krishnendu, and Georg F Osang. “Pushdown Reachability with Constant Treewidth.” Information Processing Letters. Elsevier, 2017. 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. Elsevier, 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.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
Open Access
Date Uploaded
2018-12-12
Export
Marked PublicationsOpen Data ISTA Research Explorer
Google Scholar