8494 articles  [version française]

hal-00720500, version 2

Finding a subdivision of a digraph

Jørgen Bang-Jensen 1, Frédéric Havet () 2, Ana Karolinna Maia () 2

N° RR-8024 (2012)

Abstract: We consider the following problem for oriented graphs and digraphs: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We give a number of examples of polynomial instances, several NP-completeness proofs as well as a number of conjectures and open problems.

  • 1:  Department of Mathematics and Computer Science (IMADA)
  • University of Southern Denmark
  • 2:  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
  • INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
  • Domain : Computer Science/Data Structures and Algorithms
  • Keywords : NP-completeness – 2-linkage – flows – DAG and handle decompositions.
  • Internal note : RR-8024
  • Available versions :  v1 (2012-07-24) v2 (2012-07-25)
 
  • hal-00720500, version 2
  • http://hal.inria.fr/hal-00720500
  • oai:hal.inria.fr:hal-00720500
  • From: Ana Karolinna Maia De Oliveira <>
  • Submitted on: Wednesday, 25 July 2012 11:29:35
  • Updated on: Wednesday, 25 July 2012 11:39:23