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

赋权图的w密度和w平衡性
引用本文:张胜贵,孙浩,李学良.赋权图的w密度和w平衡性[J].高校应用数学学报(英文版),2002,17(3):355-364.
作者姓名:张胜贵  孙浩  李学良
作者单位:[1]Dept.ofAppl.Math.,NorthwesternPolytechnicalUniv.,Xi'an710072,Chinat [2]CenterofCombinatorics,NankaiUniv.,Tianjin300071,China
摘    要:The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced. A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it. In this paper,a good characterization of w-balanced weighted graphs is given. Applying this characterization ,many large w-balanced weighted graphs are formed by combining smaller ones. In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed. It is shown that the w-density theory is closely related to the study of SEW(G,w) games.

关 键 词:赋权图  w密度  w平衡性  图表
收稿时间:11 September 2000

w-Density and w-balanced property of weighted graphs
Zhang Shenggui,Sun Hao,Li Xueliang.w-Density and w-balanced property of weighted graphs[J].Applied Mathematics A Journal of Chinese Universities,2002,17(3):355-364.
Authors:Zhang Shenggui  Sun Hao  Li Xueliang
Institution:(1) Dept. of Appl. Math., Northwestern Polytechnical Univ., 710072 Xi’an, China;(2) Center of Combinatorics, Nankai Univ., 300071 Tianjin, China
Abstract:The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced. A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it. In this paper, a good characterization of w-balanced weighted graphs is given. Applying this characterization, many large w-balanced weighted graphs are formed by combining smaller ones. In the case where a graph is not w-balanced, a polynomial-time algorithm to find a subgraph of maximum w-density is proposed. It is shown that the w-density theory is closely related to the study of SEW (G,w) games. Supported by the National Natural Science Foundation of China (10101021).
Keywords:05C85  05C90  05C99
本文献已被 维普 万方数据 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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