| 寻找无向图中回路的并行算法 |
| |
| 引用本文： | 马军,岩间一雄,马绍汉.寻找无向图中回路的并行算法[J].软件学报,1997,8(6):475-480. |
| |
| 作者姓名： | 马军 岩间一雄 马绍汉 |
| |
| 作者单位： | 山东大学计算机系，济南,250100;九州大学工学部计算机科学与通信工程系,日本国福冈820;山东大学计算机系，济南,250100 |
| |
| 基金项目： | 本文研究得到国家自然科学基金和国家863高科技项目基金、山东省自然科学基金和日本学术振兴会论搏基金资助. |
| |
| 摘 要： | 对无向简单图Ｇ＝（Ｖ，Ｅ），｜Ｖ｜＝ｎ，｜Ｅ｜＝ｍ，给出对下述问题的ＮＣ算法：（１）寻找Ｇ中最短回路；（２）寻找Ｇ中最短偶（奇）长度回路；（３）求解Ｃｋ，ｋ＝３，４，这里Ｃｋ表示Ｇ中长度为ｋ的回路．
|
| 关 键 词： | 图论算法 回路 最短回路 并行算法 |
| 修稿时间： | 6/7/1996 12:00:00 AM |
ON THE NUMBER OF SOLUTIONS OF CERTAI |
| |
| MA Jun,Kazuo Iwama and MA Shaohan.ON THE NUMBER OF SOLUTIONS OF CERTAI[J].Journal of Software,1997,8(6):475-480. |
| |
| Authors: | MA Jun Kazuo Iwama and MA Shaohan |
| |
| Abstract: | Let G=(V,E),|V|=n,|E|=m, be an undirected simple graph, NC algorithms are given for following problems: (1) finding a shortest circuit in G ; (2) finding a shortest circuit of even (odd) length in G ; and (3) finding a C k , k =3,4, where C k is the circuit in G of k edges. |
| |
| Keywords: | Graph algorithms cycle shortest circuits parallel algorithms |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
