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-widthleavesdirected tree-widthout-branchingsminimum leaf out-branching problemMinLOB

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 and Parity Games
• DAG-width
• 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)

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

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)