کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649423 | 1342454 | 2009 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Non-planar core reduction of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We present a reduction method that reduces a graph to a smaller core graph which behaves invariant with respect to non-planarity measures like crossing number, skewness, coarseness, and thickness. The core reduction is based on the decomposition of a graph into its triconnected components and can be computed in linear time. It has applications in heuristic and exact optimization algorithms for the non-planarity measures mentioned above. Experimental results show that this strategy reduces the number of edges by 45% in average for a widely used benchmark set of graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 7, 8 April 2009, Pages 1838–1855
Journal: Discrete Mathematics - Volume 309, Issue 7, 8 April 2009, Pages 1838–1855
نویسندگان
Markus Chimani, Carsten Gutwenger,