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

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
نویسندگان
, ,