کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333166 | 688607 | 2009 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Crossing minimization in weighted bipartite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a bipartite graph G=(L0,L1,E) and a fixed ordering of the nodes in L0, the problem of finding an ordering of the nodes in L1 that minimizes the number of crossings has received much attention in literature. The problem is NP-complete in general and several practically efficient heuristics and polynomial-time algorithms with a constant approximation ratio have been suggested. We generalize the problem and consider the version where the edges have nonnegative weights. Although this problem is more general and finds specific applications in automatic graph layout problems similar to those of the unweighted case, it has not received as much attention. We provide a new technique that efficiently approximates a solution to this more general problem within a constant approximation ratio of 3. In addition we provide appropriate generalizations of some common heuristics usually employed for the unweighted case and compare their performances.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 439-452
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 439-452
نویسندگان
Olca A. Ãakıroḡlu, Cesim Erten, Ãmer KarataÅ, Melih Sözdinler,