首页> 外文期刊>Algorithmica >On Minimum Witnesses for Boolean Matrix Multiplication
【24h】

On Minimum Witnesses for Boolean Matrix Multiplication

机译:布尔矩阵乘法的最小见证

获取原文
获取原文并翻译 | 示例

摘要

Minimum witnesses for Boolean matrix multiplication play an important role in several graph algorithms. For two Boolean matrices A and B of order n, with one of the matrices having at most m nonzero entries, the fastest known algorithms for computing the minimum witnesses of their product run in either O(n~(2.575)) time or in O(n~2 + mn Iog(n~2/m)/ log~2 n) time. We present a new algorithm for this problem. Our algorithm runs either in timernO(3(3-ε)m l-1/4-ε) where ω < 2.376 is the matrix multiplication exponent, or, if fast rectangular matrix multiplication is used, in time O(n~(1.939)m~(0.318) In particular, if ω - 1 < α < 2 where m - n~α, the new algorithm is faster than both of the aforementioned algorithms.
机译:布尔矩阵乘法的最小见证人在几种图形算法中起着重要作用。对于n阶的两个布尔矩阵A和B,其中一个矩阵最多具有m个非零项,用于计算其乘积的最小见证的最快已知算法在O(n〜(2.575))时间或O中运行(n〜2 + mn Iog(n〜2 / m)/ log〜2 n)时间。我们提出了针对该问题的新算法。我们的算法在timernO(3 / n(3-ε)m l-1 /4-ε)中运行,其中ω<2.376是矩阵乘法指数,或者,如果使用快速矩形矩阵乘法,则在时间O(n〜 (1.939)m〜(0.318)特别地,如果ω-1<α<2,其中m-n〜α,则新算法比上述两种算法都快。

著录项

  • 来源
    《Algorithmica》 |2014年第2期|431-442|共12页
  • 作者

    Keren Cohen; Raphael Yuster;

  • 作者单位

    Department of Mathematics, University of Haifa, Haifa 31905, Israel;

    Department of Mathematics, University of Haifa, Haifa 31905, Israel;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Boolean matrix multiplication; Minimum witness;

    机译:布尔矩阵乘法;最低证人;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号