\(k\)-distinct in- and out-branchings in digraphs

DOI10.1016/j.jcss.2018.01.003zbMath1391.68054arXiv1612.03607OpenAlexW2789352949WikidataQ130128701 ScholiaQ130128701MaRDI QIDQ1747490

Gregory Gutin, Magnus Wahlström, Felix Reidl

Publication date: 8 May 2018

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1612.03607

zbMATH Keywords

decompositionbranchingleaffixed-parameter tractable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

The smallest number of vertices in a 2-arc-strong digraph without pair of arc-disjoint in- and out-branchings ⋮ Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs ⋮ Smallest number of vertices in a 2-arc-strong digraph without good pairs

Cites Work

• Unnamed Item
• Unnamed Item
• Parameterized algorithms for non-separating trees and branchings in digraphs
• Fundamentals of parameterized complexity
• A new algorithm for finding trees with many leaves
• Tournament pathwidth and topological containment
• FPT algorithms and kernels for the directed \(k\)-leaf problem
• A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
• The minimum spanning strong subdigraph problem is fixed parameter tractable
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Tournament minors
• Arc-disjoint paths and trees in 2-regular digraphs
• The Directed Grid Theorem
• Small degree out‐branchings
• Quasi‐transitive digraphs
• Spanning Directed Trees with Many Leaves
• Parameterized Algorithms
• Optimum branchings

This page was built for publication: \(k\)-distinct in- and out-branchings in digraphs