Minimum Leaf Out-Branching Problems

DOI10.1007/978-3-540-68880-8_23MaRDI QIDQ3511432zbMATH OpenOpenAlexFDO

Authors G. Gutin, Igor Razgon, Eun Jung Kim

Publication date 10 July 2008

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-68880-8_23

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• Minimum leaf out-branching and related problems
• On complexity of minimum leaf out-branching problem
• Spanning directed trees with many leaves
• Better Algorithms and Bounds for Directed Maximum Leaf Problems
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems

Cites work

• scientific article; zbMATH DE number 5485472 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• An algorithm for enumerating all spanning trees of a directed graph
• Better Algorithms and Bounds for Directed Maximum Leaf Problems
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Fixed-Parameter Complexity of Minimum Profile Problems
• Parameterized Algorithms for Directed Maximum Leaf Problems
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parametrized complexity theory.
• Refined memorization for vertex cover
• Spanning directed trees with many leaves
• Sur les arborescences dans un graphe oriente
• The linear arrangement problem parameterized above guaranteed value
• The minimum spanning strong subdigraph problem is fixed parameter tractable

Cited in

(10)

• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
• On complexity of minimum leaf out-branching problem
• Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
• Balanced branchings in digraphs
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Minimum leaf out-branching and related problems
• Complexity evaluation of benchmark instances for the \(p\)-median problem
• On the directed full degree spanning tree problem
• A new algorithm for finding trees with many leaves

This page was built for publication: Minimum Leaf Out-Branching Problems

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