网站地图 | 联系我们 | English | 意见反馈 | 主任信箱
 
首页 中心概况 新闻动态 科研进展 交流合作 人才培养 研究队伍 人才招聘 政策规章 数学交叉科学传播
学术报告
现在位置:首页 > 学术报告

Spanning trees with bound total excesses
【2012.10.24 9:00am,S709】

【打印】【关闭】

 2012-10-19  

  Colloquia & Seminars 

  Speaker

  Dr. Kenta Ozeki,National Institute of Informatics

  Title

  Spanning trees with bound total excesses

  Time

  2012.10.24 9:00am

  Venue

  S709

  Abstract

  For an integer k with , a tree with maximum degree at most k is called a k-tree, and a tree with at most k leaves is called a k-ended tree.
As a generalization of the above two concepts, the concept of total excess is defined as follows: For a graph T and an integer k, the total excess te(T, k) from k is defined as

te(T,K)=SUM(max{0,degT(v)-k})

where degT(v) is the degree of v in T. It is easy to see that for a tree T, T is a k-tree if and only if te(T,k) = 0, and T is a (t+2) -ended tree if and only if te(T,2) t . So using the concept of total excess, we can deal with both spanning k-trees and spanning k-ended trees at the same time.
In this talk, I will give a survey on spanning trees with bounded total excesses.

  Affiliation

  

欢迎访问国家数学与交叉科学中心 
地址:北京海淀区中关村东路55号 邮编:100190 电话: 86-10-62613242 Fax: 86-10-62616840 邮箱: ncmis@amss.ac.cn