Back to search

North Dakota State University

A Linear Delay Algorithm for Enumerating All Connected Induced Subgraphs

Abstract

dc:description.abstract

Real biological and social data is increasingly being represented as graphs. Pattern-mining-based graph learning and analysis techniques report meaningful biological subnetworks that elucidate important interactions among entities. At the backbone of these algorithms is the enumeration of pattern space. In this work, we propose an efficient algorithm for enumerating all connected induced subgraphs of an undirected graph. Building on this enumeration approach, we propose an algorithm for mining maximal cohesive subgraphs that integrates vertices' attributes with subgraph enumeration. To efficiently mine all maximal cohesive subgraphs, we propose two pruning techniques that remove futile search nodes in the enumeration tree. Experiments on synthetic and real graphs show the effectiveness of the proposed algorithm and the pruning techniques. On enumerating all connected induced subgraphs, our algorithm is several times faster than existing approaches. On dense graphs, the proposed approach is at least an order of magnitude faster than the best existing algorithm.

Degree

thesis:*
Grantor dc:publisher
North Dakota State University
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Alokshiya, Mohammed
ORCID dc:identifier.orcid

Rights

dc:rights
Statement dc:rights
  • NDSU Policy 190.6.2

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10365/29168

Chain of custody

source
Harvested from
North Dakota State University
Base URL
library.ndsu.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Alokshiya, Mohammed. A Linear Delay Algorithm for Enumerating All Connected Induced Subgraphs. North Dakota State University, 2018. https://hdl.handle.net/10365/29168