Full metadata record
DC FieldValueLanguage
dc.contributor.authorHwang, SFen_US
dc.contributor.authorChang, GJen_US
dc.date.accessioned2014-12-08T15:47:27Z-
dc.date.available2014-12-08T15:47:27Z-
dc.date.issued1998-11-01en_US
dc.identifier.issn0895-4801en_US
dc.identifier.urihttp://hdl.handle.net/11536/31808-
dc.description.abstractSuppose 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.en_US
dc.language.isoen_USen_US
dc.subjectk-neighborhood-coveringen_US
dc.subjectk-neighborhood-independenceen_US
dc.subjectchordal graphen_US
dc.subjectstrongly chordal graphen_US
dc.subjectstrong elimination orderen_US
dc.titlek-neighborhood-covering and -independence problems for chordal graphsen_US
dc.typeArticleen_US
dc.identifier.journalSIAM JOURNAL ON DISCRETE MATHEMATICSen_US
dc.citation.volume11en_US
dc.citation.issue4en_US
dc.citation.spage633en_US
dc.citation.epage643en_US
dc.contributor.department應用數學系zh_TW
dc.contributor.departmentDepartment of Applied Mathematicsen_US
dc.identifier.wosnumberWOS:000075676500008-
dc.citation.woscount3-
Appears in Collections:Articles


Files in This Item:

  1. 000075676500008.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.