Title

Finding and Listing Induced Paths and Cycles

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 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.

Inclusive pages

633-641

ISBN/ISSN

0166-218X

Comments

Permission documentation on file.

Publisher

Elsevier

Volume

161

Issue

4-5

Peer Reviewed

yes


Share

COinS