{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:07:36Z","timestamp":1753880856444,"version":"3.41.2"},"reference-count":19,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Inter. Net."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:p> In order to restore the faulty path in network more effectively, we propose the maintaining constrained path problem. Give a directed acyclic graph (DAG) [Formula: see text] with some faulty edges, where [Formula: see text], [Formula: see text]. For any positive number [Formula: see text], we give effective maintain algorithm for finding and maintaining the path between source vertex [Formula: see text] and destination [Formula: see text] with length at most [Formula: see text]. In this paper, we consider the parameters [Formula: see text] and [Formula: see text] which are used to measure the numbers of edges and vertices which are influenced by faulty edges, respectively. The main technique of this paper is to define and solve a subproblem called the one to set constrained path problem (OSCPP) which has not been addressed before. On the DAG, compared with the dynamic shortest path algorithm with time complexity [Formula: see text] [16] and the shortest path algorithm with time complexity [Formula: see text] [18], based on the algorithm for OSCPP, we develop a maintaining constrained path algorithm and improve the time complexity to [Formula: see text] in the case that all shortest paths from each vertex [Formula: see text] to [Formula: see text] have been given. <\/jats:p>","DOI":"10.1142\/s021926592150016x","type":"journal-article","created":{"date-parts":[[2021,10,18]],"date-time":"2021-10-18T18:02:46Z","timestamp":1634580166000},"source":"Crossref","is-referenced-by-count":0,"title":["Maintaining Constrained Path Problem for Directed Acyclic Graphs"],"prefix":"10.1142","volume":"21","author":[{"given":"Chenying","family":"Hao","sequence":"first","affiliation":[{"name":"College of Mathematics, Taiyuan University of Technology, Taiyuan, Shanxi 030024, P. R. China"}]},{"given":"Shurong","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Mathematics, Taiyuan University of Technology, Taiyuan, Shanxi 030024, P. R. China"}]},{"given":"Weihua","family":"Yang","sequence":"additional","affiliation":[{"name":"College of Mathematics, Taiyuan University of Technology, Taiyuan, Shanxi 030024, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2021,10,12]]},"reference":[{"key":"S021926592150016XBIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90036-X"},{"key":"S021926592150016XBIB002","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1070.0231"},{"key":"S021926592150016XBIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_7"},{"key":"S021926592150016XBIB004","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"S021926592150016XBIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2018.04.018"},{"key":"S021926592150016XBIB006","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00205-3"},{"key":"S021926592150016XBIB007","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90328-Q"},{"key":"S021926592150016XBIB008","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1048"},{"key":"S021926592150016XBIB009","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009224"},{"key":"S021926592150016XBIB010","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"S021926592150016XBIB011","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0046"},{"key":"S021926592150016XBIB012","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2014.2343914"},{"key":"S021926592150016XBIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2015.11.004"},{"key":"S021926592150016XBIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2005.11.004"},{"key":"S021926592150016XBIB015","doi-asserted-by":"publisher","DOI":"10.1109\/90.893870"},{"key":"S021926592150016XBIB016","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"S021926592150016XBIB017","doi-asserted-by":"publisher","DOI":"10.1137\/0204032"},{"key":"S021926592150016XBIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00292-2"},{"key":"S021926592150016XBIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.08.012"}],"container-title":["Journal of Interconnection Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021926592150016X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,18]],"date-time":"2021-10-18T18:02:58Z","timestamp":1634580178000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021926592150016X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":19,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["10.1142\/S021926592150016X"],"URL":"https:\/\/doi.org\/10.1142\/s021926592150016x","relation":{},"ISSN":["0219-2659","1793-6713"],"issn-type":[{"type":"print","value":"0219-2659"},{"type":"electronic","value":"1793-6713"}],"subject":[],"published":{"date-parts":[[2021,9]]},"article-number":"2150016"}}