A short note on the approximability of the maximum leaves spanning tree problem

DOI10.1016/0020-0190(94)90139-2zbMath0942.68647OpenAlexW2035040468WikidataQ29011645 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (30)

Complexity of the maximum leaf spanning tree problem on planar and regular graphs ⋮ The connected domination number of grids ⋮ Memory-efficient enumeration of constrained spanning trees ⋮ A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks ⋮ Spanning trees with a constraint on the number of leaves. A new formulation ⋮ Leafy spanning \(k\)-forests ⋮ Traceability of connected domination critical graphs ⋮ On maximum leaf trees and connections to connected maximum cut problems ⋮ The generalized definitions of the two-dimensional largest common substructure problems ⋮ On the approximability of some maximum spanning tree problems ⋮ On the approximability of some Maximum Spanning Tree Problems ⋮ A Simple 2-Approximation for Maximum-Leaf Spanning Tree ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ An exact algorithm for the maximum leaf spanning tree problem. ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ A new algorithm for finding trees with many leaves ⋮ Spanning Trees with Many Leaves in Regular Bipartite Graphs ⋮ Approximating the Maximally Balanced Connected Partition Problem in graphs ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Approximation hardness of dominating set problems in bounded degree graphs ⋮ 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 ⋮ Connected domination of regular graphs ⋮ Unnamed Item ⋮ Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems ⋮ On Finding Directed Trees with Many Leaves ⋮ Minimal spanning trees with a constraint on the number of leaves ⋮ The approximability of the weighted Hamiltonian path completion problem on a tree ⋮ Variable neighborhood search for the vertex weighted \(k\)-cardinality tree problem

Cites Work

• Completeness in approximation classes
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• Self-stabilizing systems in spite of distributed control
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A short note on the approximability of the maximum leaves spanning tree problem