文章基本信息

标题：Theory and Applications of Butterfly Network in Graph Theory
本地全文：下载
作者：Karunagaran K ; P.Sumathi ; V. Nandakumar 等
期刊名称：International Journal of Innovative Research in Science, Engineering and Technology
印刷版ISSN：2347-6710
电子版ISSN：2319-8753
出版年度：2015
卷号：4
期号：6
页码：4067
DOI：10.15680/IJIRSET.2015.0406199
出版社：S&S Publications
摘要：A path partition of a graph is a collection of vertex-disjoint paths that cover all vertices of the graph. Thepath-partition problem is to find the path-partition number p(G) of a graph G, which is the minimum cardinality of apath partition of G. Obviously G has a Hamiltonian path if and only if [2]p(G)= 1. Since the Hamiltonian path problem is NP complete forplanar graphs, bipartite graphs, chordal graphs,chordal bipartite graphs and strongly chordal graphs, so is the path-partition problem. On the other hand, the pathpartitionproblem is polynomially solvable for trees, interval graphs, circular-arc graphs, co graphs, co comparabilitygraphs, block graphs and bipartite distance hereditary graphs.
关键词：Graph; Planar graphs; Edge partition graphs; Chordal graphs; Chordal bipartite graphs and Strongly;Butterfly Network; Benes Network[1]