Conference item icon

Conference item

Computing Excluded Minors

Abstract:

By Robertson and Seymour's graph minor theorem, every minor ideal can be characterised by a finite family of excluded minors. (A minor ideal is a class of graphs closed under taking minors.) We study algorithms for computing excluded minor characterisations of minor ideals. We propose a general method for obtaining such algorithms, which is based on definability in monadic second-order logic and the decidability of the monadic second-order theory of trees. A straightforward application...

Expand abstract

Actions


Access Document


Files:

Authors


Isolde Adler More by this author
Martin Grohe More by this author
Stephan Kreutzer More by this author
Publication date:
2008
URN:
uuid:14ffec47-d9cc-4edd-9aec-ac9f2287d137
Local pid:
cs:1719

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP