Approximating Maximum Leaf Spanning Trees in Almost Linear Time
From MaRDI portal
Publication:4217304
DOI10.1006/jagm.1998.0944zbMath0919.68097OpenAlexW1993589418MaRDI QIDQ4217304
Publication date: 11 November 1998
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/603c0cc66b7391e8c29c56f6fb8ccfe8256539bf
Related Items
Complexity of the maximum leaf spanning tree problem on planar and regular graphs, The connected domination number of grids, A 2k-vertex Kernel for Maximum Internal Spanning Tree, On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem, 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, An exact algorithm for the maximum leaf spanning tree problem., An exact exponential-time algorithm for the directed maximum leaf spanning tree problem, 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, Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree, Better Algorithms and Bounds for Directed Maximum Leaf Problems, Connected Domination, Approximating the maximum internal spanning tree problem, Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems, A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs, Leafy spanning arborescences in DAGs, On connected dominating sets of restricted diameter
