On the approximability of some Maximum Spanning Tree Problems

DOI10.1016/S0304-3975(96)00265-4zbMath0912.68146MaRDI QIDQ1391300

Francesco Maffioli, Giulia Galbiati, Angelo Morzenti

Publication date: 22 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

undirected graphsspanning trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS ⋮ FPT algorithms and kernels for the directed \(k\)-leaf problem ⋮ Max-min weight balanced connected partition ⋮ Approximation algorithm for the balanced 2-connected \(k\)-partition problem ⋮ Social distancing network creation ⋮ Unnamed Item ⋮ Constructing a spanning tree with many leaves ⋮ Better Algorithms and Bounds for Directed Maximum Leaf Problems ⋮ Unnamed Item ⋮ Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems ⋮ A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completeness in approximation classes
• On finding optimal and near-optimal lineal spanning trees
• Complexity of spanning tree problems: Part I
• On the complexity of finding multi-constrained spanning trees
• Optimization, approximation, and complexity classes
• A short note on the approximability of the maximum leaves spanning tree problem
• Balancing minimum spanning trees and shortest-path trees
• Low degree spanning trees of small weight
• On approximating the longest path in a graph
• Many birds with one stone
• The NP-completeness column: An ongoing guide

This page was built for publication: On the approximability of some Maximum Spanning Tree Problems