k-distinct in- and out-branchings in digraphs
作者：
Highlights：
• Existence of out- and in-branchings which differ in at least k arcs is studied from parameterized complexity point of view.
• Problems were posed by Bang-Jensen and Yeo (2008) and Bang-Jensen et al. (2016).
• The problems are solved by showing fixed-parameter tractability of both problems.
• A new decomposition of digraphs is suggested.
摘要
•Existence of out- and in-branchings which differ in at least k arcs is studied from parameterized complexity point of view.•Problems were posed by Bang-Jensen and Yeo (2008) and Bang-Jensen et al. (2016).•The problems are solved by showing fixed-parameter tractability of both problems.•A new decomposition of digraphs is suggested.
论文关键词：Branching,Leaf,Decomposition,Fixed-parameter tractable
论文评审过程：Received 23 August 2017, Revised 10 January 2018, Accepted 12 January 2018, Available online 7 March 2018, Version of Record 30 April 2018.
论文官网地址：https://doi.org/10.1016/j.jcss.2018.01.003
