کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4652581 1632594 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding an induced subdivision of a digraph
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Finding an induced subdivision of a digraph
چکیده انگلیسی

We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) H, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether H is an oriented graph or contains 2-cycles. We announce a number of examples of polynomial instances as well as several NP-completeness results.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 37, 1 August 2011, Pages 9-14