solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看217次
Algorithms for Pattern Containment in 0-1 Matrices. (arXiv:1704.05207v1 [cs.DM])
来源于:arXiv
We say a zero-one matrix $A$ avoids another zero-one matrix $P$ if no
submatrix of $A$ can be transformed to $P$ by changing some ones to zeros. A
fundamental problem is to study the extremal function $ex(n,P)$, the maximum
number of nonzero entries in an $n \times n$ zero-one matrix $A$ which avoids
$P$. To calculate exact values of $ex(n,P)$ for specific values of $n$, we need
containment algorithms which tell us whether a given $n \times n$ matrix $A$
contains a given pattern matrix $P$. In this paper, we present optimal
algorithms to determine when an $n \times n$ matrix $A$ contains a given
pattern $P$ when $P$ is a column of all ones, an identity matrix, a tuple
identity matrix, an $L$-shaped pattern, or a cross pattern. These algorithms
run in $\Theta(n^2)$ time, which is the lowest possible order a containment
algorithm can achieve. When $P$ is a rectangular all-ones matrix, we also
obtain an improved running time algorithm, albeit with a higher order. 查看全文>>