کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4584337 | 1630481 | 2015 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The arctic rank of a Boolean matrix
ترجمه فارسی عنوان
رتبه الکتریک ماتریس بولین
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
اعداد جبر و تئوری
چکیده انگلیسی
Among different rank functions on tropical matrices, there is one known as tropical rank which is a lower bound for any other. Here we introduce a new concept (for being opposed to tropical rank, it is called arctic) which gives an upper bound for other ranks. Our definition is based on the perimeter notion previously studied for rank-one matrices. We study the arithmetic behavior of the arctic rank and compare it with that of other rank functions. Finally, we provide an algorithm computing the arctic rank. We show that no algorithm is likely to find the arctic rank in polynomial time by proving that computing the perimeter of a matrix is an NP-hard problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algebra - Volume 433, 1 July 2015, Pages 168–182
Journal: Journal of Algebra - Volume 433, 1 July 2015, Pages 168–182
نویسندگان
LeRoy B. Beasley, Alexander E. Guterman, Yaroslav Shitov,