On complexity of minimum leaf out-branching problem

DOI10.1016/J.DAM.2009.04.012MaRDI QIDQ967352zbMATH OpenOpenAlexFDO

Authors G. Gutin, Eun Jung Kim, Peter Dankelmann

Publication date 28 April 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.04.012

zbMATH Keywords

computational complexityDAG-widthdirected tree-widthleavesminimum leaf out-branching problemMinLOBout-branchings

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Minimum Leaf Out-Branching Problems
• Minimum leaf out-branching and related problems
• Spanning directed trees with many leaves
• Better Algorithms and Bounds for Directed Maximum Leaf Problems
• Branching in digraphs with many and few leaves: structural and algorithmic results

Cites work

• DAG-width
• DAG-Width and Parity Games
• Digraph Decompositions and Monotonicity in Digraph Searching
• Digraph measures: Kelly decompositions, games, and orderings
• Directed path-width and monotonicity in digraph searching
• Directed tree-width
• Minimum Leaf Out-Branching Problems
• On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
• Spanning directed trees with many leaves
• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree

Cited in

(12)

• Minimum leaf out-branching and related problems
• Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
• Linear kernels for outbranching problems in sparse digraphs
• Digraph width measures in parameterized algorithmics
• An algorithmic metatheorem for directed treewidth
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
• Minimum Leaf Out-Branching Problems
• On digraph width measures in parameterized algorithmics
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• On the minimum caterpillar problem in digraphs
• Directed nowhere dense classes of graphs
• Directed elimination games

This page was built for publication: On complexity of minimum leaf out-branching problem

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