A short note on the approximability of the maximum leaves spanning tree problem
From MaRDI portal
Publication:1336751
DOI10.1016/0020-0190(94)90139-2zbMath0942.68647WikidataQ29011645 ScholiaQ29011645MaRDI QIDQ1336751
Angelo Morzenti, Giulia Galbiati, Francesco Maffioli
Publication date: 26 February 1996
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)90139-2
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Spanning Trees with Many Leaves in Regular Bipartite Graphs, A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs, Unnamed Item, Leafy spanning trees in hypercubes, Max-leaves spanning tree is APX-hard for cubic graphs, A new algorithm for finding trees with many leaves, Approximating the Maximally Balanced Connected Partition Problem in graphs, Approximation hardness of dominating set problems in bounded degree graphs, Reformulations and solution algorithms for the maximum leaf spanning tree problem, Connected domination of regular graphs, Minimal spanning trees with a constraint on the number of leaves, On the approximability of some Maximum Spanning Tree Problems, An exact algorithm for the maximum leaf spanning tree problem., A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks, The approximability of the weighted Hamiltonian path completion problem on a tree, Variable neighborhood search for the vertex weighted \(k\)-cardinality tree problem, Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems, On Finding Directed Trees with Many Leaves
Cites Work
