Parameterized algorithms for non-separating trees and branchings in digraphs

DOI10.1007/s00453-015-0037-3zbMath1353.68106OpenAlexW1052559269MaRDI QIDQ334949

Saket Saurabh, Sven Simonsen, Jörgen Bang-Jensen

Publication date: 1 November 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0037-3

zbMATH Keywords

partitioning problemspanning treebranchingparameterized complexityfixed-parameter tractableexponential-time algorithmlinear vertex kernel

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The smallest number of vertices in a 2-arc-strong digraph without pair of arc-disjoint in- and out-branchings, \(k\)-distinct in- and out-branchings in digraphs, Smallest number of vertices in a 2-arc-strong digraph without good pairs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arc-disjoint spanning sub(di)graphs in digraphs
• On the tractability of some natural packing, covering and partitioning problems
• Exact exponential algorithms.
• FPT algorithms and kernels for the directed \(k\)-leaf problem
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• The minimum spanning strong subdigraph problem is fixed parameter tractable
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• A linear vertex kernel for maximum internal spanning tree
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Sharp separation and applications to exact and parameterized algorithms
• Arc-disjoint paths and trees in 2-regular digraphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• Kernel(s) for problems with no kernel
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Spanning Directed Trees with Many Leaves
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Digraphs