Takumi Tada

dblp:340/3674 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2025
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 2 since 2021
YearPublicationVenuePosition
2025 A linear delay algorithm in SD set system and its application to subgraph enumeration
abstract
For a set system ( V , C ⊆ 2 V ) , we call each C ∈ C a component. A nonempty subset Y ⊊ C is a removable set (RS) of C if C ∖ Y is a component. We say that a set system has subset-disjoint (SD) property if, for any two components C , C ′ with C ′ ⊊ C , every minimal RS Y of C satisfies either Y ⊆ C ′ or Y ∩ C ′ = ∅ . Assuming that an SD set system is implicitly given by an oracle that returns a minimal RS of a component, we provide an algorithm that enumerates all components in linear time/space with respect to | V | and oracle running time/space. We then extend this algorithm to linear-delay enumeration of all 2-edge-connected (or 2-vertex-connected) induced subgraphs in an undirected graph and of all strongly connected subgraphs in a digraph.
Takumi Tada, Kazuya Haraguchi
J. Comput. Syst. Sci.1
2023 A Linear Delay Algorithm for Enumeration of 2-Edge/Vertex-Connected Induced Subgraphs
Takumi Tada, Kazuya Haraguchi
IWOCA1