{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:20:27Z","timestamp":1753885227409,"version":"3.41.2"},"reference-count":14,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:p> For a connected graph [Formula: see text] and a fixed integer [Formula: see text], a node [Formula: see text] [Formula: see text]-dominates another node [Formula: see text] if [Formula: see text]. An edge [Formula: see text] is [Formula: see text]-neighborhood covered by a vertex [Formula: see text], if [Formula: see text] and [Formula: see text], i.e., both the vertices [Formula: see text] and [Formula: see text] are [Formula: see text]-dominated by the vertex [Formula: see text]. A set [Formula: see text] is known to be a [Formula: see text]-neighborhood covering ([Formula: see text]-NC) set of graph [Formula: see text] if and only if one or more vertices of [Formula: see text] [Formula: see text]-dominate each edge in E. Among all [Formula: see text]-NC sets of graph [Formula: see text], the set with fewest cardinality is the minimum [Formula: see text]-NC set of [Formula: see text] and we indicate its cardinality as [Formula: see text]-NC-number and we denote it by the symbol [Formula: see text]. This is an NP-complete problem on general graphs. It is also NP-complete for chordal graphs. Here, we develop an [Formula: see text] time algorithm for computing a minimum [Formula: see text]-NC set of permutation graphs, where [Formula: see text] indicates the order of the set [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s1793830921500816","type":"journal-article","created":{"date-parts":[[2020,12,23]],"date-time":"2020-12-23T03:58:12Z","timestamp":1608695892000},"source":"Crossref","is-referenced-by-count":0,"title":["Minimum r-neighborhood covering set of permutation graphs"],"prefix":"10.1142","volume":"13","author":[{"given":"Amita Samanta","family":"Adhya","sequence":"first","affiliation":[{"name":"Research Centre in Natural Sciences, (Department of Computer Science), Raja N. L. Khan Women\u2019s College (Autonomous), Midnapore 721102, India"}]},{"given":"Sukumar","family":"Mondal","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Raja N. L. Khan Women\u2019s College (Autonomous), Midnapore 721102, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6662-5172","authenticated-orcid":false,"given":"Sambhu Charan","family":"Barman","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Shahid Matangini Hazra Govt. College for Women, Purba Medinipur 721649, India"}]}],"member":"219","published-online":{"date-parts":[[2021,1,25]]},"reference":[{"key":"S1793830921500816BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/s12190-008-0218-1"},{"key":"S1793830921500816BIB002","doi-asserted-by":"publisher","DOI":"10.1080\/00207160802676570"},{"key":"S1793830921500816BIB003","doi-asserted-by":"publisher","DOI":"10.1137\/0406002"},{"issue":"1","key":"S1793830921500816BIB004","first-page":"15","volume":"9","author":"Ghosh P. K.","year":"2007","journal-title":"Adv. Model. Optim."},{"volume-title":"Algorithmic Graph Theory and Perfect Graphs","year":"1980","author":"Golumbic M. C.","key":"S1793830921500816BIB005"},{"key":"S1793830921500816BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90365-O"},{"key":"S1793830921500816BIB007","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193244322"},{"key":"S1793830921500816BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(86)90031-2"},{"key":"S1793830921500816BIB009","doi-asserted-by":"publisher","DOI":"10.1080\/00207160211921"},{"key":"S1793830921500816BIB010","doi-asserted-by":"publisher","DOI":"10.1145\/58562.59300"},{"key":"S1793830921500816BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90245-D"},{"key":"S1793830921500816BIB012","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1971-016-5"},{"issue":"3","key":"S1793830921500816BIB013","first-page":"463","volume":"13","author":"Rana A.","year":"2011","journal-title":"Adv. Model. Opt."},{"key":"S1793830921500816BIB014","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830921500816","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,8]],"date-time":"2021-12-08T11:34:05Z","timestamp":1638963245000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830921500816"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,25]]},"references-count":14,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["10.1142\/S1793830921500816"],"URL":"https:\/\/doi.org\/10.1142\/s1793830921500816","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2021,1,25]]},"article-number":"2150081"}}