scientific article; zbMATH DE number 1305098
From MaRDI portal
Publication:4252040
zbMath0932.68069MaRDI QIDQ4252040
Publication date: 13 March 2000
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Complexity of the maximum leaf spanning tree problem on planar and regular graphs ⋮ A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks ⋮ On finding spanning trees with few leaves ⋮ FPT algorithms and kernels for the directed \(k\)-leaf problem ⋮ Flow-based formulation for the maximum leaf spanning tree problem ⋮ Leafy spanning \(k\)-forests ⋮ On maximum leaf trees and connections to connected maximum cut problems ⋮ A 3-approximation algorithm for the maximum leaf \(k\)-forest problem ⋮ A Simple 2-Approximation for Maximum-Leaf Spanning Tree ⋮ Improved bounds for spanning trees with many leaves ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ Dominating complex networks by identifying minimum skeletons ⋮ Optimal wake-up scheduling of data gathering trees for wireless sensor networks ⋮ An exact algorithm for the maximum leaf spanning tree problem. ⋮ How heavy independent sets help to find arborescences with many leaves in DAGs ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ A new algorithm for finding trees with many leaves ⋮ Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree ⋮ A Local-Search Algorithm for Steiner Forest ⋮ Spanning Trees with Many Leaves in Regular Bipartite Graphs ⋮ Spanning trees: A survey ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Leafy spanning trees in hypercubes ⋮ A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs ⋮ Reformulations and solution algorithms for the maximum leaf spanning tree problem ⋮ Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms ⋮ Better Algorithms and Bounds for Directed Maximum Leaf Problems ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ Connected domination of regular graphs ⋮ Approximating the maximum internal spanning tree problem ⋮ Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems ⋮ On Finding Directed Trees with Many Leaves ⋮ A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs ⋮ Leafy spanning arborescences in DAGs ⋮ Approximating spanning trees with few branches
