Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights

DOI10.7155/jgaa.00279zbMath1254.68126OpenAlexW2005483893MaRDI QIDQ5894785

Bart M. P. Jansen

Publication date: 7 December 2012

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00279

zbMATH Keywords

max leaf spanning tree problemweighted max leaf

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

A \(9k\) kernel for nonseparating independent set in planar graphs ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Leafy spanning arborescences in DAGs

This page was built for publication: Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights