کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874714 1441190 2018 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Reconfiguration in bounded bandwidth and tree-depth
ترجمه فارسی عنوان
تنظیم در پهنای باند محدود و عمق درخت
کلمات کلیدی
تنظیمات دوباره رنگ کردن، درخت عرض پهنای باند درخت عمق، هموروئید گراف
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that several reconfiguration problems known to be PSPACE-complete remain so even when limited to graphs of bounded bandwidth (and hence pathwidth and treewidth). The essential step is noticing the similarity to very limited string rewriting systems, whose ability to directly simulate Turing Machines is classically known. On the other hand, we show that a large class of natural reconfiguration problems (coming from graph homomorphisms) becomes tractable on graphs of bounded tree-depth, and prove a dichotomy showing this to be in some sense tight.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 93, May 2018, Pages 1-10
نویسندگان
,