کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428335 686637 2007 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On transitive orientations with restricted covering graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On transitive orientations with restricted covering graphs
چکیده انگلیسی

We consider the problem of finding a transitive orientation of a comparability graph, such that the edge set of its covering graph contains a given subset of edges. We propose a solution which employs the classical technique of modular tree decomposition. The method leads to a polynomial time algorithm to construct such an orientation or report that it does not exist.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 101, Issue 3, 14 February 2007, Pages 119-125