The neighbor-scattering number can be computed in polynomial time for interval graphs

Simple item page
dc.creatorLi, Fengwei
dc.creatorLi, Xueliang
dc.date2006-03-17
dc.date.accessioned2026-07-07T07:05:51Z
dc.date.available2026-07-07T07:05:51Z
dc.descriptionNeighbor-scattering number is a useful measure for graph vulnerability. For some special kinds of graphs, explicit formulas are given for this number. However, for general graphs it is shown that to compute this number is NP-complete. In this paper, we prove that for interval graphs this number can be computed in polynomial time.
dc.description13 pages
dc.identifierhttps://arxiv.org/abs/cs/0603069
dc.identifierhttp://arxiv.org/abs/cs/0603069
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/109815
dc.subjectDiscrete Mathematics
dc.subjectCombinatorics
dc.subjectG.2.2; F.2.2
dc.titleThe neighbor-scattering number can be computed in polynomial time for interval graphs
dc.typetext

Files

Collections

arXiv