• Title of article

    New results on planar and directed multicuts

  • Author/Authors

    Bentz، نويسنده , , Cédric، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2009
  • Pages
    5
  • From page
    207
  • To page
    211
  • Abstract
    We show that the multicut problem is APX-hard in directed acyclic graphs, even with three source-sink pairs. We also show that it is tractable in planar graphs with a fixed number of terminals, and even FPT if all the terminals lie on the outer face.
  • Keywords
    APX-hardness , multicuts , graph algorithms
  • Journal title
    Electronic Notes in Discrete Mathematics
  • Serial Year
    2009
  • Journal title
    Electronic Notes in Discrete Mathematics
  • Record number

    1455106

    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=10&DC=1455106