Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights

DOI10.1007/978-3-642-13073-1_18MaRDI QIDQ5900911zbMATH OpenOpenAlexFDO

Authors Bart M. P. Jansen

Publication date 28 May 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.216.1851

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Kernelization for maximum leaf spanning tree with positive vertex weights
• A linear vertex kernel for maximum internal spanning tree
• A linear vertex kernel for Maximum Internal Spanning Tree
• A 2k-vertex kernel for maximum internal spanning tree
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Kernelization for maximum happy vertices problem
• Maximum of k-th maximal spanning trees of a weighted graph
• scientific article; zbMATH DE number 2080206
• The maximum-leaf spanning tree problem: Formulations and facets
• An exact algorithm for the maximum leaf spanning tree problem

Cited in

(4)

• Simpler linear-time kernelization for planar dominating set
• Kernel(s) for problems with no kernel
• Kernelization for maximum leaf spanning tree with positive vertex weights
• Parameterized approximation algorithms and lower bounds for k-center clustering and variants

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5900911)