標題: ALGORITHMIC ASPECTS OF NEIGHBORHOOD NUMBERS
作者: CHANG, GJ
FARBER, M
TUZA, Z
應用數學系
Department of Applied Mathematics
關鍵字: NEIGHBORHOOD-COVERING;NEIGHBORHOOD-INDEPENDENCE;CLIQUE-TRANSVERSAL;CLIQUE-INDEPENDENCE;CHORDAL GRAPH;STRONGLY CHORDAL GRAPH;SPLIT GRAPH;NP-COMPLETE
公開日期: 1-Feb-1993
摘要: In a graph G = (V, E), E[v] denotes the set of edges in the subgraph induced by N[v] = {v} or {u is-an-element-of V: uv is-an-element-of E}. The neighborhood-covering problem is to find the minimum cardinality of a set C of vertices such that E = or {E[v]: v is-an-element-of C}. The neighborhood-independence problem is to find the maximum cardinality of a set of edges in which there are no two distinct edges belonging to the same E[v] for any v is-an-element-of V. Two other related problems are the clique-transversal problem and the clique-independence problem. It is shown that these four problems are NP-complete in split graphs with degree constraints and linear time algorithms for them are given in a strongly chordal graph when a strong elimination order is given.
URI: http://dx.doi.org/10.1137/0406002
http://hdl.handle.net/11536/3122
ISSN: 0895-4801
DOI: 10.1137/0406002
期刊: SIAM JOURNAL ON DISCRETE MATHEMATICS
Volume: 6
Issue: 1
起始頁: 24
結束頁: 29
Appears in Collections:Articles


Files in This Item:

  1. A1993KL99800002.pdf