Finding and Listing Induced Paths and Cycles
Discrete Applied Mathematics
Many recognition problems for special classes of graphs and cycles can be reduced to finding and listing induced paths and cycles in a graph. We design algorithms to list all P3's in O(m1.5+p3(G)) time and for k ≥ 4 all Pk's in O(nk-1+pk(G)+k*ck(G)) time, where pk(G), respectively,ck(G), are the numbers of Pk's, respectively Ck's, of a graph G. We also provide an algorithm to find a Pk, k ≥ 5, in time O(k!!*m(k-1)/2) if k is odd, and O(k!!*nm(k/2)-1) if k is even. As applications of our findings, we give algorithms to recognize quasi-triangulated graphs and brittle graphs. Our algorithms’ time bounds are incomparable with previously known algorithms.
Copyright © 2012, Elsevier
Hoàng, Chính T.; Kamiński, Marcin; Sawada, Joe; and Sritharan, R., "Finding and Listing Induced Paths and Cycles" (2013). Computer Science Faculty Publications. 170.