Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs.
Andrzej GrzesikTereza KlimosováMarcin PilipczukMichal PilipczukPublished in: SODA (2019)
Keyphrases
- independent set
- maximum weight
- bipartite graph
- computational complexity
- worst case
- optimal solution
- objective function
- weighted graph
- dynamic programming
- special case
- learning algorithm
- np hard
- minimum weight
- graph structure
- bipartite matching
- probabilistic model
- graph theory
- polynomial time complexity
- maximum independent set