کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649467 1342457 2009 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A dynamic distributed approach to representing proper interval graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A dynamic distributed approach to representing proper interval graphs
چکیده انگلیسی

First studied by Brodal and Fagerberg [G.S. Brodal, R. Fagerberg, Dynamic representation of sparse graphs, in: Algorithms and Data Structures, Proceedings of the 6th International Workshop, Vancouver, Canada, in: Lecture Notes in Computer Science, vol. 1663, Springer-Verlag, 1999], a dynamic adjacency labelling scheme labels the vertices of a graph so that the adjacency of two vertices can be deduced from their labels. The scheme is dynamic in the sense that only a small adjustment must be made to the vertex labels when a small change is made to the graph.Using a centralized dynamic representation of Hell, Shamir and Sharan [P. Hell, R. Shamir, R. Sharan, A fully dynamic algorithm for recognizing and representing proper interval graphs, SIAM Journal on Computing 31 (1) (2001) 289–305], we develop a O(logn) bit/label dynamic adjacency labelling scheme for proper interval graphs. Our fully dynamic scheme handles vertex deletion/addition and edge deletion/addition in O(n) time. Furthermore, our dynamic scheme is error-detecting, as it recognizes when the new graph is not a proper interval graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 18, 28 September 2009, Pages 5697–5702
نویسندگان
,