Testing for a theta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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 languageEnglish (US)
Title of host publicationProceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
PublisherAssociation for Computing Machinery
Pages595-598
Number of pages4
ISBN (Electronic)9780898716245
StatePublished - Jan 1 2007
Event18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States
Duration: Jan 7 2007Jan 9 2007

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume07-09-January-2007

Other

Other18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
CountryUnited States
CityNew Orleans
Period1/7/071/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.