Minimum Leaf Out-Branching Problems
From MaRDI portal
Publication:3511432
DOI10.1007/978-3-540-68880-8_23zbMATH Open1143.90391OpenAlexW1912364756MaRDI QIDQ3511432FDOQ3511432
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
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
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)
Cites Work
- Parametrized complexity theory.
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Title not available (Why is that?)
- Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
- The linear arrangement problem parameterized above guaranteed value
- Sur les arborescences dans un graphe oriente
- Title not available (Why is that?)
- An algorithm for enumerating all spanning trees of a directed graph
- Title not available (Why is that?)
- The minimum spanning strong subdigraph problem is fixed parameter tractable
- Spanning directed trees with many leaves
- Refined memorization for vertex cover
- Parameterized Algorithms for Directed Maximum Leaf Problems
- Better Algorithms and Bounds for Directed Maximum Leaf Problems
- Fixed-Parameter Complexity of Minimum Profile Problems
Cited In (10)
- A new algorithm for finding trees with many leaves
- Minimum leaf out-branching and related problems
- On complexity of minimum leaf out-branching problem
- Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
- On the directed full degree spanning tree problem
- Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
- Complexity evaluation of benchmark instances for the \(p\)-median problem
- Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
- Balanced branchings in digraphs
- Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
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)
