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
Authors
Bibliographic Details
- Host title:
- ACM−SIAM Symposium on Discrete Algorithms (SODA)
- Publication date:
- 2008-01-01
Item Description
- UUID:
-
uuid:14ffec47-d9cc-4edd-9aec-ac9f2287d137
- Local pid:
-
cs:1719
- Deposit date:
-
2015-03-31
Terms of use
- Copyright date:
- 2008
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record