Parameterized algorithms for non-separating trees and branchings in digraphs

DOI10.1007/S00453-015-0037-3zbMATH Open1353.68106OpenAlexW1052559269MaRDI QIDQ334949FDOQ334949

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

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

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)

Cites Work

• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Exact exponential algorithms.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Title not available (Why is that?)
• Digraphs
• Title not available (Why is that?)
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• FPT algorithms and kernels for the directed \(k\)-leaf 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
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Kernel(s) for problems with no kernel
• Arc-disjoint spanning sub(di)graphs in digraphs
• On the tractability of some natural packing, covering and partitioning problems
• Spanning directed trees with many leaves
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem

Cited In (11)

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

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)