VLDB 2026 Research / reviewers in the wild / expert
Kan Shota
dblp:381/4260
· DBLP profile ↗
2ranked-venue papers
2as first author
2since 2021 · last 2026
0009-0004-2447-4160ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 2 first-author · 2 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | A linear-delay algorithm for enumerating strongly-connected induced subgraphs based on SSD set systemabstractIn this paper, we first study what we call Superset-Subset-Disjoint (SSD) set system. Based on properties of SSD set system, we derive the following (I) to (IV): (I) For a nonnegative integer $k$ and a graph $G=(V,E)$ with $|V|\ge2$, let $X_1,X_2,\dots,X_q\subsetneq V$ denote all maximal proper subsets of $V$ that induce $k$-edge-connected subgraphs. Then at least one of (a) and (b) holds: (a) $\{X_1,X_2,\dots,X_q\}$ is a partition of $V$; and (b) $V\setminus X_1, V\setminus X_2,\dots,V\setminus X_q$ are pairwise disjoint. (II) For $k=1$ and a strongly-connected digraph $G$, whether $V$ is in (a) and/or (b) can be decided in $O(n+m)$ time and we can generate all such $X_1,X_2,\dots,X_q$ in $O(n+m+|X_1|+|X_2|+\dots+|X_q|)$ time, where $n=|V|$ and $m=|E|$. (III) For a digraph $G$, we can enumerate in linear delay all vertex subsets of $V$ that induce strongly-connected subgraphs. (IV) A digraph is Hamiltonian if there is a spanning subgraph that is strongly-connected and in the case (a). Kan Shota, Kazuya Haraguchi |
J. Comput. Syst. Sci. | 1 |
| 2025 | A Linear Delay Algorithm of Enumerating Strongly-Connected Induced Subgraphs Based on SSD Set System
Kan Shota, Kazuya Haraguchi |
IWOCA | 1 |