COOMA: A Components Overlaid Mining Algorithm for Enumerating Connected Subgraphs with Common Itemsets Kazuya Haraguchi, Yusuke Momoi, Aleksandar Shurbevski, and Hiroshi Nagamochi Vol. 23, no. 2, pp. 434-458, 2019. Regular paper. Abstract In the present paper, we consider the graph mining problem of enumerating what we call connectors. Suppose that we are given a data set $(G,I,\sigma)$ that consists of a graph $G=(V,E)$, an item set $I$, and a function $\sigma:V\rightarrow 2^{I}$. For $X\subseteq V$, we define $A_\sigma(X)\triangleq\bigcap_{v\in X}\sigma(v)$. Note that, for $X,Y\subseteq V$, $X\subseteq Y$ implies that $A_\sigma(X)\supseteq A_\sigma(Y)$. A vertex subset $X$ is called a connector if (i) the subgraph $G[X]$ induced from $G$ by $X$ is connected; and (ii) for any $v\in V\setminus X$, $G[X\cup\{v\}]$ is disconnected or $A_\sigma(X\cup\{v\})\subsetneq A_\sigma(X)$. To enumerate all connectors, we propose a novel algorithm named COOMA (components overlaid mining algorithm). The algorithm mines connectors by "overlaying" an already discovered connector on a certain subgraph of $G$ iteratively. By overlaying, we mean taking an intersection between the connector and connected components of a certain induced subgraph. Interestingly, COOMA is a total-polynomial time algorithm, i.e., the running time is polynomially bounded with respect to the input and output size. We show the efficiency of COOMA in comparison with COPINE [Sese et al., 2010], a depth-first-search based algorithm. Submitted: January 2019. Reviewed: April 2019. Revised: June 2019. Accepted: July 2019. Final: July 2019. Published: July 2019. Communicated by Seok-Hee Hong article (PDF) BibTeX