| 权守恒有向图中的最小总权圈 |
| |
| 引用本文： | 由巧俐,唐恒永.权守恒有向图中的最小总权圈[J].沈阳师范大学学报(自然科学版),2006,24(1):10-12. |
| |
| 作者姓名： | 由巧俐 唐恒永 |
| |
| 作者单位： | 沈阳师范大学,数学与系统科学学院,辽宁,沈阳,110034 |
| |
| 摘 要： | 讨论权守恒的有向图中最小总权圈问题,分别给出求解一般情况下最小总权圈的最优算法和经过特定点或特定边情况下最小总权圈的最优算法.另外还给出判定是否有圈经过特定点或特定边的线性时间算法.
|
| 关 键 词： | 圈 最小总权 算法复杂性 |
| 文章编号： | 1008-374X(2006)01-0010-03 |
| 收稿时间： | 2005-02-23 |
| 修稿时间： | 2005年2月23日 |
A Circuit of Minimum Total Weight in a Digraph |
| |
| YOU Qiao-li,TANG Heng-yong.A Circuit of Minimum Total Weight in a Digraph[J].Journal of Shenyang Normal University: Nat Sci Ed,2006,24(1):10-12. |
| |
| Authors: | YOU Qiao-li TANG Heng-yong |
| |
| Institution: | College of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110004, China |
| |
| Abstract: | In this paper we consider the circuit of minimum total weight problem.It is assumed that the weights of a graph are conservative.Optimal algorithms are presented respectively for circuit of minimum total weight,and circuit of minimum total weight traversing a specific vertex or a specific edge.Moreover we give algorithms for determining whether there is a circuit traversing a specific vertex or edge in linear time. |
| |
| Keywords: | circuit minimum total weight complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
