MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEFinding an (induced) subdivision of a digraph
par F. Havet
| Date : | 22/02/11 | | Time : | 10:30 | | Location : | Euler Bleu |
Ă‚' We consider the following problems for digraphs: Given a digraph G, does it contain a subdivision of a prescribed digraph D?
does it contain an induced subdivision of D?
The complexity of these problems depends on D.
Moreover the complexity of the second one depends on whether H must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP- completeness proofs.
Joint work with J. Bang-Jensen and N. Trotignon
Page des séminaires
| 
