On the Steiner medians of a block graph

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/7865

Title:	On the Steiner medians of a block graph
Authors:	彭勝鴻;Sheng-Hueng Peng
Contributors:	數學研究所
Keywords:	block graph;the Steiner n-median;the Steiner n-distance
Date:	2005-06-01
Issue Date:	2009-09-22 11:07:34 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	在圖論中，若有某一點屬於median，則代表的是此點到其他所有的點之平均距離是最短的。事實上，一般圖論上所定義的median即是Steiner n – median中n = 2的特殊型態。但是，除了樹以外，到目前為止我們仍然無法很快速的找出任意圖形的Steiner n – median。　　本篇論文主要把圖形著重在block graph上，從其找出一個只需多項式時間就能找出Steiner n – median的演算法，並推導出一個找出所有Steiner n – distance的值的方法。　　最後一個部份則是舉無窮多個同類的圖來說明對於任意正整數ｎ，並不是所有的圖形的n – median都有包含的關係；以及一個簡單的n – median值下界。 The Steiner distance of anmpty set of vertices S of a connected graph G is the minimum number of edges of G containing S. Let n ? 2 be an integer and suppose that G has at least n vertices. The Steiner n – distance of a vertex v of G is defined to be the sum of the Steiner distances of all sets of n vertices that include v. Then the Steiner n – median of G is the subgraph induced by the vertices of minimum Steiner n – distance. In this paper, we present a O(\|V(B)\| + \|E(B)\|) algorithm for finding the Steiner n – median of a block graph B and present an efficient algorithm for finding the Steiner n – distance of all vertices in a block graph. Finial, we given an infinite family of graphs in which each graph G has M2(G) ? M3(G). And we given a trivial lower bounded for the Steiner n – median value.
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...