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 (9)

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

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