Finding and Listing Induced Paths and Cycles

Author(s)

Chính T. Hoàng, Wilfrid Laurier University
Marcin Kamiński, Universite Libre de Bruxelles
Joe Sawada, University of Guelph
R. Sritharan, University of DaytonFollow

Document Type

Article

Publication Date

3-2013

Publication Source

Discrete Applied Mathematics

Abstract

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 P₃'s in O(m^1.5+p₃(G)) time and for k ≥ 4 all P_k's in O(n^k-1+p_k(G)+k*c_k(G)) time, where p_k(G), respectively,c_k(G), are the numbers of P_k's, respectively C_k's, of a graph G. We also provide an algorithm to find a P_k, 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.

Inclusive pages

633-641

ISBN/ISSN

0166-218X

Comments

Permission documentation on file.

Copyright

Copyright © 2012, Elsevier

Publisher

Elsevier

Volume

161

Peer Reviewed

yes

Issue

4-5

eCommons Citation

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.
https://ecommons.udayton.edu/cps_fac_pub/170