Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems

DOI10.1016/j.endm.2009.02.011zbMath1267.05260OpenAlexW1971373505MaRDI QIDQ2839214

Gregory Gutin

Publication date: 4 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.02.011

zbMATH Keywords

kernelFPTleavesout-branchingsout-treesinternal vertices

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Improved bounds for spanning trees with many leaves ⋮ Spanning 3-ended trees in almost claw-free graphs ⋮ The existence of spanning ended system on claw-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arbres avec un nombre maximum de sommets pendants
• Approximation hardness of dominating set problems in bounded degree graphs
• On complexity of minimum leaf out-branching problem
• Constructing full spanning trees for cubic graphs
• Spanning trees in graphs of minimum degree 4 or 5
• A short note on the approximability of the maximum leaves spanning tree problem
• On the approximability of some Maximum Spanning Tree Problems
• Directed tree-width
• Parametrized complexity theory.
• Kernel(s) for problems with no kernel
• Minimum Leaf Out-Branching Problems
• On Problems without Polynomial Kernels (Extended Abstract)
• Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree
• A New Algorithm for Finding Trees with Many Leaves
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Approximation algorithms for connected dominating sets
• Spanning Directed Trees with Many Leaves
• Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
• Parameterized Algorithms for Directed Maximum Leaf Problems
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Better Algorithms and Bounds for Directed Maximum Leaf Problems
• Digraphs
• Algorithms and Data Structures

This page was built for publication: Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems