Minimum Leaf Out-Branching Problems

DOI10.1007/978-3-540-68880-8_23zbMath1143.90391MaRDI QIDQ3511432

Eun Jung Kim, Igor Razgon, Gregory Gutin

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

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

Related Items

Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem, On the directed full degree spanning tree problem, Complexity evaluation of benchmark instances for the \(p\)-median problem, A new algorithm for finding trees with many leaves, On complexity of minimum leaf out-branching problem, Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem, Balanced branchings in digraphs, Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems, Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Refined memorization for vertex cover
• The minimum spanning strong subdigraph problem is fixed parameter tractable
• Sur les arborescences dans un graphe oriente
• An algorithm for enumerating all spanning trees of a directed graph
• The linear arrangement problem parameterized above guaranteed value
• Parametrized complexity theory.
• Fixed-Parameter Complexity of Minimum Profile Problems
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Spanning Directed Trees with Many Leaves
• Parameterized Algorithms for Directed Maximum Leaf Problems
• Better Algorithms and Bounds for Directed Maximum Leaf Problems