报告内容简介:In this talk, we consider the constrained rural postman problem on mixed graphs. We use $Q^+$ and $Z^+$ to denote the sets of positive rational numbers and positive integers, respectively. For any mixed graph $G=(V,E\cup A;w;l,u)$ with two required subsets $E'\subseteq E$ and $A'\subseteq A$, where a length function \map w {E\cup A} {Q^+} and two integer functions \map {l,u} {E'\cup A'} {Z^+}, satisfying $l(e) \leq u(e)$ for each edge $e\in E'\cup A'$, we are asked to determine a minimum length tour $C$ traversing each edge $e\in E'\cup A'$ at least $l(e)$ and at most $u(e)$ times.Our main results are as follows. (1) We present a few facts that they are {\it NP}-hard to determine feasible tours for the constrained rural postman problem specialized on digraphs for some special cases. (2) We design a $3$-approximation algorithm to solve this problem specialized on graphs. This work is jointed with Xiaofei Liu.
主持人:吕长虹 教授