Decomposing Weighted Graphs |
| |
Authors: | Amir Ban |
| |
Affiliation: | BLAVATNIK SCHOOL OF COMPUTER SCIENCE, TEL AVIV UNIVERSITY, TEL AVIV, ISRAEL |
| |
Abstract: | We solve the following problem: Can an undirected weighted graph G be partitioned into two nonempty induced subgraphs satisfying minimum constraints for the sum of edge weights at vertices of each subgraph? We show that this is possible for all constraints satisfying , for every vertex x , where are, respectively, the sum and maximum of incident edge weights. |
| |
Keywords: | weighted partition decomposition |
|
|