检索结果-南通市图书馆

作者：徐灵志中南大学

学位级别：硕士

图搜索算法是通过图中的边对图中所有顶点进行系统访问的过程。研究人员根据不同的搜索策略设计了六种搜索算法,包括深度优先搜索、广度优先搜索、极大邻域搜索、字典序深度优先搜索、字典序广度优先搜索和最大基数搜索。图搜索算法可... 详细信息

图搜索算法是通过图中的边对图中所有顶点进行系统访问的过程。研究人员根据不同的搜索策略设计了六种搜索算法,包括深度优先搜索、广度优先搜索、极大邻域搜索、字典序深度优先搜索、字典序广度优先搜索和最大基数搜索。图搜索算法可以从给定图的任意点开始访问,但是哪些点可以成为搜索的结束点,这个问题在近十余年引起了人们的关注,即图搜索算法终点问题。这六种图搜索算法终点问题均被证明是NP完全问题。本文研究了图搜索终点问题在cograph上的算法和复杂性,主要贡献如下。第一,本文证明了cograph上的深度优先搜索和广度优先搜索终点问题是线性时间可解的。对于cograph上的深度优先搜索终点问题,本文研究了它与最小路径覆盖问题的关系,并结合cograph的最小路径覆盖数给出了cograph上深度优先搜索终点问题的刻画;本文设计了更加高效的用于计算cograph最小路径覆盖数的线性时间算法,并结合该算法设计了可在线行时间求解cograph上深度优先搜索终点问题的算法。对于广度优先搜索终点问题,本文证明了cograph上的任意非全局点都可以成为广度优先搜索终点,且对一般图上的全局点也给出了该问题的刻画。并结合这两点进一步证明了该问题在cograph上具有线性时间的求解算法。第二,本文为cograph上的极大邻域搜索、字典序广度优先搜索和最大基数搜索终点问题也提出了线性时间的解决方案。对于极大邻域搜索算法终点问题和字典序广度优先搜索算法终点问题,本文证明了它们在cograph上有着相同的刻画,即在cograph的树形表示方法(Cotree)中满足一个特定结构。本文还发现使用字典序广度优先搜索及其变种的两次扫描可以验证这个结构,并分别基于cotree和字典序广度优先搜索设计了两个线性时间的判定算法。对于最大基数搜索算法终点问题,本文利用cograph的多种模块性质设计了一种基于cotree的自底向上的求解算法,并证明该算法的时间复杂度是线性的。图4幅,表1个,参考文献91篇。

关键词：搜索算法搜索序列终点问题 cograph

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs

引用

Journal of Computer Science & Technology 2009年第3期24卷 517-533页

作者： Shin-ichi Nakano Ryuhei Uehara Takeaki Uno Department of Computer Science Faculty of EngineeringGunma UniversityGunma 376-8515Japan School of Information Science Japan Advanced Institute of Science and TechnologyIshikawa 923-1292Japan National Institute of Informatics Tokyo 101-8430Japan

Algorithms used in data mining and bioinformatics have to deal with huge amount of data efficiently. In many applications, the data are supposed to have explicit or implicit structures. To develop efficient algorithms for such data, we have to propose possible structure models and test if the models are feasible. Hence, it is important to make a compact model for structured data, and enumerate all instances efficiently. There are few graph classes besides trees that can be used for a model. In this paper, we investigate distance-hereditary graphs. This class of graphs consists of isometric graphs and hence contains trees and cographs. First, a canonical and compact tree representation of the class is proposed. The tree representation can be constructed in linear time by using prefix trees. Usually, prefix trees are used to maintain a set of strings. In our algorithm, the prefix trees are used to maintain the neighborhood of vertices, which is a new approach unlike the lexicographically breadth-first search used in other studies. Based on the canonical tree representation, efficient algorithms for the distance-hereditary graphs are proposed, including linear time algorithms for graph recognition and graph isomorphism and an efficient enumeration algorithm. An efficient coding for the tree representation is also presented; it requires [3.59n] bits for a distance-hereditary graph of n vertices and 3n bits for a cograph. The results of coding improve previously known upper bounds （both are 2^O（nlogn）） of the number of distance-hereditary graphs and cographs to 2^[3.59n] and 2^3n, respectively.

关键词： algorithmic graph theory cograph distance-hereditary graph prefix tree tree representation

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

2-Structures理论和图的模块分解中的若干问题

2-Structures理论和图的模块分解中的若干问题

引用

作者：程科上海交通大学

学位级别：硕士

图论和组合数学是离散数学中的重要组成部分,在解决计算机中的算法和生物结构以及其他学科问题中都发挥着重要的作用,因此研究一个图的结构性质也显得更加重要了 2-Structures理论和图的模块分解理论是在自然科学与数学中出现的一... 详细信息

图论和组合数学是离散数学中的重要组成部分,在解决计算机中的算法和生物结构以及其他学科问题中都发挥着重要的作用,因此研究一个图的结构性质也显得更加重要了 2-Structures理论和图的模块分解理论是在自然科学与数学中出现的一种重要的结构,它们在求解图的最优化问题中、算法图论、计算机科学、生物数学等领域都有着广泛的应用。同时图的2-Structures理论是研究图的分解理论的框架和基础,如对完全图的边着色问题。对图的modular decomposition研究主要产生于对不同的离散结构的探讨,如无向图、有向图、2-Structures, automata, Boolean functions, hypergraphs。图的modular decomposition在图论中有很多重要的应用,例如它能给出一个给定的可比较图的所有可传递方向计算框架;定义一些图类如cographs, P4-sparse或者P4-tidy。本文首先对2-Structures理论中的经典理论进行了回顾。接着整理了2-Structures的shape的基本性质,以及2-Structures-labeled tree family与labeled 2-Structures之间的关系和性质。并就2-Structures理论中的若干引理和推论给出了新的证明并对定理2.3.27进行了推广。然后我们引入了图的module和]nodular decomposition理论,并对原有的理论进行了整理。接着讨论了图的module的基本性质,图的modular decomposition的一些重要定理。通过对图的module和modular decomposition理论的深入研究,结合自己的理解,得到了一些新结果。如对于一般简单图,它的任何两个模块之间的关系（定理3.3.1）;对于一般简单图,如果此图是素图（即不含有非平凡的模块-所有模块都是平凡的）,那么此图关于平凡模块的商图在图的同构的意义下是一样的（定理3.3.6）;如果图G是非初等素图,那么图G一定含有P4诱导的路径（定理3.3.7）;对于一简单图G在满足某种条件下,其模块分解树一定是一棵二叉树（定理3.3.14）;以及P4是最小的非初等素图（推论3.3.15）和观察（3.3.9）：i)根据图的模块分解的定义,任何图都具有图的模块分解树;ii)如果对于一个顶点个数不小于4的简单连通图,如果其模块分解树是一棵二叉树,那么此图一定不是素图,且其不含有标号是N-node的节点;iii)对于任何图,按其最大非初等模块分解得到相应图的商图,如此递推下去,最终只有两类图：素图和一个点的图;完全图的模块分解树是所有图中模块分树中深度最大的分解树,同时素图的模块分分解树是深度最小的。最后给出了2-Structures和图的module及其modular decomposition之间的某些联系。

关键词： 2-structures clans 图的模块图的模块分解图的模块分解树 cograph Cotree

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：