### Abstract

In this paper we survey some known results on the question of testing whether a given graph contains certian induced subgraphs. We also present a new algorithm, to test if a graph contains a special kind of an induced subgraph, called a "theta".

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 |

Publisher | Association for Computing Machinery |

Pages | 595-598 |

Number of pages | 4 |

ISBN (Electronic) | 9780898716245 |

State | Published - Jan 1 2007 |

Event | 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States Duration: Jan 7 2007 → Jan 9 2007 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 07-09-January-2007 |

### Other

Other | 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 |
---|---|

Country | United States |

City | New Orleans |

Period | 1/7/07 → 1/9/07 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Testing for a theta'. Together they form a unique fingerprint.

## Cite this

Chudnovsky, M., & Seymour, P. (2007). Testing for a theta. In

*Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007*(pp. 595-598). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 07-09-January-2007). Association for Computing Machinery.