Spanning Directed Trees with Many Leaves
From MaRDI portal
Publication:5189530
DOI10.1137/070710494zbMath1215.05027OpenAlexW1974096415WikidataQ60488751 ScholiaQ60488751MaRDI QIDQ5189530
Gregory Gutin, Saket Saurabh, Fedor V. Fomin, Michael Krivelevich, Noga Alon
Publication date: 17 March 2010
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070710494
Trees (05C05) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Leader selection for strong structural controllability of single-integrator multi-agent systems ⋮ FPT algorithms and kernels for the directed \(k\)-leaf problem ⋮ Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ Some results on spanning trees ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Minimum Leaf Out-Branching Problems ⋮ How heavy independent sets help to find arborescences with many leaves in DAGs ⋮ On the directed full degree spanning tree problem ⋮ A new algorithm for finding trees with many leaves ⋮ \(k\)-distinct in- and out-branchings in digraphs ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ On complexity of minimum leaf out-branching problem ⋮ Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems ⋮ On Finding Directed Trees with Many Leaves ⋮ Basic Terminology, Notation and Results ⋮ Acyclic Digraphs ⋮ Leafy spanning arborescences in DAGs
