Pushdown reachability with constant treewidth

Chatterjee K, Osang GF. 2017. Pushdown reachability with constant treewidth. Information Processing Letters. 122, 25–29.

Download
OA IST-2018-991-v1+2_2018_Chatterjee_Pushdown_PREPRINT.pdf 247.66 KB [Submitted Version]

Journal Article | Published | English

Scopus indexed
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. 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)
Access Level
OA Open Access
Date Uploaded
2018-12-12


Export

Marked Publications

Open Data ISTA Research Explorer

Web of Science

View record in Web of Science®

Search this title in

Google Scholar