An algorithm for identifying Morishima and anti-Morishima matrices and balanced digraphs (Q1059646)

We present an algorithm for identifying Morishima and anti-Morishima matrices. Since Morishima matrices have signed digraphs that are balanced, our algorithm also identifies such digraphs. We actually work with a signed graph and our algorithm is a depth first traversal with certain markers added to keep track of parsing of nodes and signs of edges. The algorithm is, of course, linear in the amount of input.