標題: k-neighborhood-covering and -independence problems for chordal graphs
作者: Hwang, SF
Chang, GJ
應用數學系
Department of Applied Mathematics
關鍵字: k-neighborhood-covering;k-neighborhood-independence;chordal graph;strongly chordal graph;strong elimination order
公開日期: 1-十一月-1998
摘要: Suppose G = (V, E) is a simple graph and k is a fixed positive integer. A vertex z k-neighborhood-covers an edge (x, y) if d(z, x) less than or equal to k and d(z, y) less than or equal to k. A k-neighborhood-covering set is a set C of vertices such that every edge in E is k-neighborhood-covered by some vertex in C. A k-neighborhood-independent set is a set of edges in which no two distinct edges can be k-neighborhood-covered by the same vertex in V. In this paper we first prove that the neighborhood-covering and the k-neighborhood-independence problems are NP-complete for chordal graphs. We then present a linear-time algorithm for finding a minimum k-neighborhood-covering set and a maximum k-neighborhood-independent set for a strongly chordal graph provided that a strong elimination ordering is given in advance.
URI: http://hdl.handle.net/11536/31808
ISSN: 0895-4801
期刊: SIAM JOURNAL ON DISCRETE MATHEMATICS
Volume: 11
Issue: 4
起始頁: 633
結束頁: 643
顯示於類別:期刊論文


文件中的檔案:

  1. 000075676500008.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。