Toshihide Ibaraki

Describes a new, logic-based methodology for analyzing observations. The key features of this “logical analysis of data” (LAD) methodology are the discovery of minimal sets of features that are necessary for explaining all observations and the detection of hidden patterns in the data that are capable of distinguishing observations describing “positive” outcome events from “negative” outcome events. Combinations of such patterns are used for developing general classification procedures. An implementation of this methodology is described in this paper, along with the results of numerical experiments demonstrating the classification performance of LAD in comparison with the reported results of other procedures. In the final section, we describe three pilot studies on applications of LAD to oil exploration, psychometric testing and the analysis of developments in the Chinese transitional economy. These pilot studies demonstrate not only the classification power of LAD but also its flexibility and capability to provide solutions to various case-dependent problems.

Given an undirected graph $G = ( V,E )$, it is known that its edge-connectivity $\lambda ( G )$ can be computed by solving $O( | V | )$ max-flow problems. The best time bounds known for the problem are $O( \lambda ( G ) | V |^2 )$, due to Matula (28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 249–251) if G is simple, and $O( | E |^{3/2} | V | )$, due to Even and Tarjan (SIAM J. Comput., 4 (1975), pp. 507–518) if G is multiple. An $O( | E | + \min \{ \lambda ( G ) | V |^2 ,p | V | + | V |^2 \log | V | \} )$ time algorithm for computing the edge-connectivity $\lambda ( G )$ of a multigraph $G = ( V,E )$, where $p ( \leqq | E | )$ is the number of pairs of nodes between which G has an edge, is proposed. This algorithm does not use any max-flow algorithm but consists only of $| V |$ times of graph searches and edge contractions. This method is then extended to a capacitated network to compute its minimum cut capacity in $O ( | V | | E | + | V |^2 \log | V | )$ time.