Record number :
Title of article :
Finding an induced subdivision of a digraph
Author/Authors :
Bang-Jensen، نويسنده , , Jّrgen and Havet، نويسنده , , Frédéric and Trotignon، نويسنده , , Nicolas، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2011
Pages :
From page :
To page :
Abstract :
We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) H, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether H is an oriented graph or contains 2-cycles. We announce a number of examples of polynomial instances as well as several NP-completeness results.
Keywords :
digraphs , NP-Completeness , linkings , induced paths and cycles
Journal title :
Electronic Notes in Discrete Mathematics
Serial Year :
Link To Document :