کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651431 | 1342545 | 2006 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimal fill in O(n2.69)O(n2.69) time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We show that it is possible to find a minimal fill ordering of a graph in O(n2.69)O(n2.69) time. Previous algorithms for the problem required Ω(n3)Ω(n3) time on dense graphs. The algorithm uses fast matrix multiplication to produce the same ordering of vertices as Tarjan's well known LEX-M algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 3, 28 February 2006, Pages 366–371
Journal: Discrete Mathematics - Volume 306, Issue 3, 28 February 2006, Pages 366–371
نویسندگان
Dieter Kratsch, Jeremy Spinrad,