Weighted coloring on planar, bipartite and split graphs: Complexity and approximation.
Dominique de WerraMarc DemangeBruno EscoffierJérôme MonnotVangelis Th. PaschosPublished in: Discret. Appl. Math. (2009)
Keyphrases
- graph model
- approximation error
- weighted graph
- graph partitioning
- bipartite graph
- approximation algorithms
- undirected graph
- worst case
- graph structure
- directed graph
- complex structures
- graph representation
- edge weights
- maximum weight
- error tolerance
- error bounds
- decision problems
- neural network
- association graph
- polynomial time complexity