首页   系科介绍   师资队伍   科研团队   本科生教学   研究生培养   招聘信息   联系我们

Previous Next
 
首页 >> 学术报告

Parameterized Complexity of the k-arc Chinese Postman Problem

盛斌 博士(伦敦大学计算机系)
2016年10月31号19:00-20:00  闵行三教214
 
摘要:In the Mixed Chinese Postman Problem (MCPP), given an edge-weighted mixed graph G (G may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges was known to be fixed-parameter tractable using a simple argument. Solving an open question of van Bevern et al., we prove that the MCPP parameterized by the number of arcs is also fixed-parameter tractable. Our proof is more involved and, in particular, uses a very useful result of Marx, O’Sullivan and Razgon (2013) on the treewidth of torso graphs with respect to small separators.
   
 
 
快捷链接 >>
 
系内资源 >>
 
教学园地 >>
 
  校外链接 >>    上海市核心数学与基础数学重点实验室    华师大-纽大联合数学中心    上海市数学会    中国数学会    美国数学会    欧洲数学会  
         
       Copyright 2012 All rights reserved    Department of Mathematics, East China Normal University    Tel: 86-21-54342609