On the approximability of some maximum spanning tree problems

DOI10.1007/3-540-59175-3_97zbMath1495.68172OpenAlexW2174799808MaRDI QIDQ5096340

Francesco Maffioli, Angelo Morzenti, Giulia Galbiati

Publication date: 16 August 2022

Published in: LATIN '95: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59175-3_97

Mathematics Subject Classification ID

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

Cites Work

• 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
• Low degree spanning trees of small weight
• On approximating the longest path in a graph
• Many birds with one stone

This page was built for publication: On the approximability of some maximum spanning tree problems