Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs.
Ahmad BiniazPublished in: CoRR (2020)
Keyphrases
- spanning tree
- approximation algorithms
- minimum cost
- undirected graph
- minimum weight
- weighted graph
- maximum weight
- minimum spanning tree
- np hard
- independent set
- special case
- minimum spanning trees
- graph matching
- worst case
- vertex cover
- edge disjoint
- bipartite graph
- edge weights
- constant factor
- graph structure
- probabilistic model
- directed graph