Home Contact Chinese CAS
Home  About Us    Research     People   International Cooperation   News     Papers   Education & Training  Join Us
Location: Home > Research > Colloquia & Seminars
Spanning trees with bound total excesses【2012.10.24 9:00am,S709】
 Date:18-10-2012 Page Views:
Print
Text Size: A A A
Close

 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

  

[ Close ]  [ Top ]
  Copyright © 2012, All Rights Reserved, National Center for Mathematics and Interdisciplinary Sciences, CAS
Tel: 86-10-62613242 Fax: 86-10-62616840 E-mail: ncmis@amss.ac.cn