首页 | 本学科首页   官方微博 | 高级检索  
     


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 urn:x-wiley:03649024:media:jgt22124:jgt22124-math-0001 satisfying urn:x-wiley:03649024:media:jgt22124:jgt22124-math-0002, for every vertex x , where urn:x-wiley:03649024:media:jgt22124:jgt22124-math-0003 are, respectively, the sum and maximum of incident edge weights.
Keywords:weighted  partition  decomposition
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号