| 摘要: |
| 对无向简单图Ｇ＝（Ｖ，Ｅ），｜Ｖ｜＝ｎ，｜Ｅ｜＝ｍ，给出对下述问题的ＮＣ算法：（１）寻找Ｇ中最短回路；（２）寻找Ｇ中最短偶（奇）长度回路；（３）求解Ｃｋ，ｋ＝３，４，这里Ｃｋ表示Ｇ中长度为ｋ的回路． |
| 关键词: 图论算法 回路 最短回路 并行算法 |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国家自然科学基金和国家863高科技项目基金、山东省自然科学基金和日本学术振兴会论搏基金资助. |
|
| ON THE NUMBER OF SOLUTIONS OF CERTAI |
|
MA Jun,Kazuo Iwama,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. |
| Key words: Graph algorithms cycle shortest circuits parallel algorithms. |
