کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419556 | 683840 | 2010 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An implicit representation of chordal comparability graphs in linear time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An implicit representation of chordal comparability graphs in linear time An implicit representation of chordal comparability graphs in linear time](/preview/png/419556.png)
چکیده انگلیسی
Ma and Spinrad have shown that every transitive orientation of a chordal comparability graph is the intersection of four linear orders. That is, chordal comparability graphs are comparability graphs of posets of dimension four. Among other uses, this gives an implicit representation of a chordal comparability graph using O(n)O(n) integers so that, given two vertices, it can be determined in O(1)O(1) time whether they are adjacent, no matter how dense the graph is. We give a linear time algorithm for finding the four linear orders, improving on their bound of O(n2)O(n2).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 8, 28 April 2010, Pages 869–875
Journal: Discrete Applied Mathematics - Volume 158, Issue 8, 28 April 2010, Pages 869–875
نویسندگان
Andrew R. Curtis, Clemente Izurieta, Benson Joeris, Scott Lundberg, Ross M. McConnell,