Parameterized algorithms for non-separating trees and branchings in digraphs

DOI10.1007/S00453-015-0037-3MaRDI QIDQ334949zbMATH OpenOpenAlexFDO

Authors 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

branchingparameterized complexityspanning treefixed-parameter tractableexponential-time algorithmlinear vertex kernelpartitioning problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3917707
• Fixed-Parameter Tractability for Non-Crossing Spanning Trees
• Branching and Treewidth Based Exact Algorithms
• A decomposition algorithm for noncrossing trees
• scientific article; zbMATH DE number 902730
• Branching in digraphs with many and few leaves: structural and algorithmic results
• Non-deterministic graph searching in trees
• Dynamic algorithms for graphs of bounded treewidth
• Dynamic algorithms for graphs of bounded treewidth

Cites work

• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 3313442 (Why is no real title available?)
• A linear vertex kernel for maximum internal spanning tree
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Arc-disjoint paths and trees in 2-regular digraphs
• Arc-disjoint spanning sub(di)graphs in digraphs
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Digraphs
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Exact exponential algorithms.
• FPT algorithms and kernels for the directed \(k\)-leaf problem
• Kernel(s) for problems with no kernel
• On the tractability of some natural packing, covering and partitioning problems
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• Sharp separation and applications to exact and parameterized algorithms
• Spanning directed trees with many leaves
• The minimum spanning strong subdigraph problem is fixed parameter tractable
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(11)

• K-distinct branchings admits a polynomial kernel
• FPT algorithms for packing \(k\)-safe spanning rooted sub(di)graphs
• Smallest number of vertices in a 2-arc-strong digraph without good pairs
• Non-separating spanning trees and out-branchings in digraphs of independence number 2
• Fixed-Parameter Tractability for Non-Crossing Spanning Trees
• A blossoming algorithm for tree volumes of composite digraphs
• \(k\)-distinct in- and out-branchings in digraphs
• \(k\)-distinct in- and out-branchings in digraphs
• A Parametrized Analysis of Algorithms on Hierarchical Graphs
• The smallest number of vertices in a 2-arc-strong digraph without pair of arc-disjoint in- and out-branchings
• The complexity of finding arc-disjoint branching flows

This page was built for publication: Parameterized algorithms for non-separating trees and branchings in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334949)