Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00357
A Polynomial Delay Algorithm for Generating Connected Induced Subgraphs of a Given Cardinality
Khaled Elbassioni
Vol. 19, no. 1, pp. 273-280, 2015. Regular paper.
Abstract We give a polynomial delay algorithm, that for any graph G and positive integer k, enumerates all connected induced subgraphs of G of order k. Our algorithm enumerates each subgraph in at most O((kmin{(n−k),k∆})2(∆+logk)) and uses linear space O(n+m), where n and m are respectively the number of vertices and edges of G and ∆ is the maximum degree.
|
Submitted: January 2014.
Reviewed: April 2015.
Revised: April 2015.
Accepted: April 2015.
Final: May 2015.
Published: May 2015.
Communicated by
Prosenjit K. Bose
|
Journal Supporters
|