Approximating Maximum Leaf Spanning Trees in Almost Linear Time
From MaRDI portal
Recommendations
- A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
- scientific article; zbMATH DE number 1947432
- scientific article; zbMATH DE number 1305098
- An approximation algorithm for the maximum leaf spanning arborescence problem
- An exact algorithm for the maximum leaf spanning tree problem.
Cited in
(42)- Approximating the maximum internal spanning tree problem
- On finding optimal and near-optimal lineal spanning trees
- An exact algorithm for the maximum leaf spanning tree problem.
- Dominating complex networks by identifying minimum skeletons
- Leafy spanning \(k\)-forests
- On connected dominating sets of restricted diameter
- A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks
- On finding spanning trees with few leaves
- On maximum leaf trees and connections to connected maximum cut problems
- A 3-approximation algorithm for the maximum leaf \(k\)-forest problem
- Complexity of the maximum leaf spanning tree problem on planar and regular graphs
- Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
- Approximation algorithms for the maximum leaf spanning tree problem on acyclic digraphs
- An approximation algorithm for the maximum leaf spanning arborescence problem
- scientific article; zbMATH DE number 6611438 (Why is no real title available?)
- Flow-based formulation for the maximum leaf spanning tree problem
- Connected domination
- 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
- Improved bounds for spanning trees with many leaves
- Max-leaves spanning tree is APX-hard for cubic graphs
- scientific article; zbMATH DE number 1305098 (Why is no real title available?)
- scientific article; zbMATH DE number 1496857 (Why is no real title available?)
- An exact exponential-time algorithm for the directed maximum leaf spanning tree problem
- Better approximations for tree sparsity in nearly-linear time
- Complexity of spanning tree problems with leaf-dependent objectives
- A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
- A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
- Spanning Trees with Many Leaves in Regular Bipartite Graphs
- A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs
- Better Algorithms and Bounds for Directed Maximum Leaf Problems
- Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
- Leafy spanning trees in hypercubes
- Leafy spanning arborescences in DAGs
- A Simple 2-Approximation for Maximum-Leaf Spanning Tree
- Spanning trees: A survey
- Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
- Network fault costs based on minimum leaf spanning trees
- The connected domination number of grids
- FPT algorithms and kernels for the directed k-leaf problem
- Approximating optimum branchings in linear time
- Reformulations and solution algorithms for the maximum leaf spanning tree problem
This page was built for publication: Approximating Maximum Leaf Spanning Trees in Almost Linear Time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4217304)
