کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438165 | 690234 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A linear edge kernel for two-layer crossing minimization
ترجمه فارسی عنوان
یک هسته لبه خطی برای به حداقل رساندن عبور دو لایه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
به حداقل رسیدن عبور پارامتر ثابت قابل ردیابی طراحی گراف کرنل کردن، طراحی دو لایه
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The two-layer crossing minimization problem (TLCM), given a bipartite graph G with n vertices and a positive integer k, asks whether G has a two-layer drawing with at most k crossings. We consider a simple generalization of TLCM called leaf-edge-weighted TLCM (LEW-TLCM), where we allow positive weights on edges incident to leaves, and show that this problem admits a kernel with O(k)O(k) edges provided that the given graph is connected. As a straightforward consequence, LEW-TLCM (and hence TLCM) has a fixed parameter algorithm that runs in 2O(klogk)+nO(1)2O(klogk)+nO(1) time which improves on the previously best known algorithm with running time 2O(k3)n2O(k3)n.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 554, 16 October 2014, Pages 74–81
Journal: Theoretical Computer Science - Volume 554, 16 October 2014, Pages 74–81
نویسندگان
Yasuaki Kobayashi, Hirokazu Maruta, Yusuke Nakae, Hisao Tamaki,