Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs.
Ahmad BiniazPublished in: J. Graph Algorithms Appl. (2022)
Keyphrases
- spanning tree
- approximation algorithms
- minimum cost
- undirected graph
- minimum weight
- maximum weight
- minimum spanning trees
- np hard
- independent set
- weighted graph
- minimum spanning tree
- special case
- edge weights
- worst case
- directed graph
- randomized algorithms
- edge disjoint
- bipartite graph
- graph theory
- planar graphs
- lower bound