On complexity of minimum leaf out-branching problem

DOI10.1016/j.dam.2009.04.012zbMath1211.05161OpenAlexW2155539817MaRDI QIDQ967352

Eun Jung Kim, Gregory Gutin, 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

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

Related Items

An algorithmic metatheorem for directed treewidth, Linear kernels for outbranching problems in sparse digraphs, Directed elimination games, Digraph width measures in parameterized algorithmics, On the algorithmic effectiveness of digraph decompositions and complexity measures, Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials, Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems, On Digraph Width Measures in Parameterized Algorithmics, Unnamed Item

Cites Work

• Unnamed Item
• Directed tree-width
• Directed path-width and monotonicity in digraph searching
• Minimum Leaf Out-Branching Problems
• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
• DAG-width
• On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
• Spanning Directed Trees with Many Leaves
• Digraph Decompositions and Monotonicity in Digraph Searching
• DAG-Width and Parity Games