کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431610 688594 2015 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Interval graph representation with given interval and intersection lengths
ترجمه فارسی عنوان
نمایندگی نمودار فاصله با فاصله داده شده و طول تقاطع
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We consider the problem of finding interval graph representations that additionally respect given interval lengths and/or pairwise intersection lengths, which are represented as weight functions on the vertices and edges, respectively. Pe'er and Shamir (1997 [25]) proved that the problem is NPNP-complete if only the former are given. For the case when both are given, Fulkerson and Gross (1965 [8]) gave an O(n2)O(n2) time algorithm; we improve this to O(n+m)O(n+m) time and supplement it with a logspace algorithm. For the case when only the latter are given, we give both an O(nm)O(nm) time algorithm and a logspace algorithm. In all these bounds, n is the number of vertices and m is the number of edges in the input graph.Complementing their hardness result, Pe'er and Shamir give a polynomial-time algorithm for the case that the input graph has a unique interval ordering of its maximal cliques. For such graphs, their algorithm computes an interval representation (if it exists) that respects a given set of distance inequalities between the interval endpoints. We observe that deciding if such a representation exists is NLNL-complete.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 34, September 2015, Pages 108–117
نویسندگان
, , ,