On the approximability of some Maximum Spanning Tree Problems
From MaRDI portal
Publication:1391300
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)
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