کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874447 | 1441160 | 2018 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Encoding partial orders through modular decomposition
ترجمه فارسی عنوان
رمزگذاری جزئی دستورات از طریق تجزیه مدولار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let P be a poset and S be a set of elements. A well-known method for representing P is called a bit-vector encoding and consists in associating to each element of P a subset of S such that the order relation between two elements coincides with their subsets inclusion. The size of this encoding is |S| and it determines both space and time needed to store and compare the poset's elements. As a consequence, this encoding has found applications for handling hierarchies in databases, distributed computing, object-oriented programming languages, etc. The computation of the smallest size of a bit-vector encoding of a poset, called the 2-dimension, is an NP-hard problem. Thus, researches deal with heuristics that provide tight bounds or an approximation of this parameter. Our paper introduces new classes of trees whose the 2-dimension is either known or 2-approximated. Moreover, it presents a new heuristic for partial orders encoding through the modular decomposition. This unified process is a 4-approximation for the 2-dimension of rooted trees and provides reduced encoding by almost 40% for series-parallel posets. It reaches or improves the best results for general posets.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computational Science - Volume 25, March 2018, Pages 446-455
Journal: Journal of Computational Science - Volume 25, March 2018, Pages 446-455
نویسندگان
Laurent Beaudou, Kaoutar Ghazi, Giacomo Kahn, Olivier Raynaud, Eric Thierry,