Minimum Leaf Out-Branching Problems

DOI10.1007/978-3-540-68880-8_23zbMath1143.90391OpenAlexW1912364756MaRDI 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

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

Related Items (9)

Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem ⋮ 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 ⋮ 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

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

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