標題: | 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 |
顯示於類別: | 期刊論文 |