一些组合地图新算法的实现(英文)  

Implements of Some New Algorithms for Combinatorial Maps

作　　者：王涛[1] 刘彦佩[2] 

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044 [2]北京交通大学理学院,北京100044

出　　处：《运筹学学报》2008年第2期58-66,共9页Operations Research Transactions

基　　金：the National Natural Science Foundation of China(No.60373030).

摘　　要：本文主要讨论组合地图列举问题.刘的一部专著中提出了一个判定两个地图是否同构的算法.该算法的时间复杂度为O(m2),其中m为下图的规模.在此基础上,本文给出一个用于地图列举以及进而计算任意连通下图的地图亏格分布的通用算法.本文所得结果比之前文献中所给结果更优.This paper is concerned with map enumeration problem by a computer. A theoretical algorithm for determining two maps isomorphic has been presented in one of Liu＇s monographs. The complexity of the isomorphic algorithm is O（m^2） where m is the size of the under graph. Based on this the first implement of the general algorithm for map enumeration and further for genus distribution of maps with a connected under graph is obtained. The results are shown to have more advantages than those in literature as known up to now.

关 键 词：运筹学 图 地图 曲面 嵌入 同构 算法 

分 类 号：O177.91[理学—数学] TP391.41[理学—基础数学]