{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T09:44:19Z","timestamp":1753868659637,"version":"3.41.2"},"reference-count":34,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2018,8,14]],"date-time":"2018-08-14T00:00:00Z","timestamp":1534204800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61402033"],"award-info":[{"award-number":["61402033"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005022","name":"Beijing Jiaotong University","doi-asserted-by":"publisher","award":["2017JBM022"],"award-info":[{"award-number":["2017JBM022"]}],"id":[{"id":"10.13039\/501100005022","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2019,1,10]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>Finding link\/node\u2010disjoint paths between a pair of nodes is capable of providing Quality of Service and reliable routing which is very critical for mesh\u2010connected Network\u2010on\u2010Chip. State\u2010of\u2010art works usually aim at random topologies and multiple constraints. Therefore, it is difficult to optimize their time complexity. In this paper, MDPPIM (Manhattan\u2010distance\u2010constrained Disjoint Path Pair Problem in Incomplete Mesh) problem is presented based on Network\u2010on\u2010Chip application scenarios. Then, PCDP (Path\u2010Counting Disjoint Path) algorithm is proposed to solve the MDPPIM problem with low time complexity. Compared with previous disjoint path algorithms, PCDP algorithm does not have to use Dijkstra's algorithm to find a shortest path. It is optimized according to the feature of incomplete mesh such as the regularity of mesh and Manhattan\u2010distance constraint. Therefore, it is with low time complexity. Numerical results demonstrate the proposed PCDP algorithm's effectiveness and low time complexity.<\/jats:p>","DOI":"10.1002\/cpe.4799","type":"journal-article","created":{"date-parts":[[2018,8,14]],"date-time":"2018-08-14T22:07:16Z","timestamp":1534284436000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An efficient Manhattan\u2010distance\u2010constrained disjoint paths algorithm for incomplete mesh network"],"prefix":"10.1002","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2190-7130","authenticated-orcid":false,"given":"Hongzhi","family":"Zhao","sequence":"first","affiliation":[{"name":"Beijing Key Lab of Transportation Data Analysis and Mining School of Computer and Information Technology, Beijing Jiaotong University Beijing 100044 China"}]},{"given":"Yongchang","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Key Lab of Transportation Data Analysis and Mining School of Computer and Information Technology, Beijing Jiaotong University Beijing 100044 China"}]},{"given":"Ke","family":"Xiong","sequence":"additional","affiliation":[{"name":"Beijing Key Lab of Transportation Data Analysis and Mining School of Computer and Information Technology, Beijing Jiaotong University Beijing 100044 China"}]},{"given":"Lihua","family":"Song","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology North China University of Technology Beijing 100144 China"}]}],"member":"311","published-online":{"date-parts":[[2018,8,14]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.1996.4772741"},{"key":"e_1_2_7_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2012.2235188"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.2007.909768"},{"key":"e_1_2_7_5_1","doi-asserted-by":"crossref","unstructured":"YangY QuanH ShiZ ZengX YuZ.Modified minimal\u2010connected\u2010component fault block model to deal with defective links and nodes for 2D\u2010mesh NoCs. Paper presented at: 9th IEEE International Conference on ASIC;2011;Xiamen China.","DOI":"10.1109\/ASICON.2011.6157173"},{"key":"e_1_2_7_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxw040"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2016.2591798"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3852"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.4218\/etrij.09.0108.0531"},{"issue":"3","key":"e_1_2_7_10_1","first-page":"347","article-title":"Dynamic multi constraint multi path QOS routing algorithm (DMCMPRA)","volume":"32","author":"Leela R","year":"2010","journal-title":"Int J Comput Appl"},{"key":"e_1_2_7_11_1","doi-asserted-by":"crossref","unstructured":"DoP\u2010T NguyenT\u2010D PhamQ\u2010D.An efficient exact algorithm for finding two link\u2010disjoint paths with related path cost and QoS constraint. In: Proceedings of the Second Symposium on Information and Communication Technology;2011;Hanoi Vietnam.","DOI":"10.1145\/2069216.2069225"},{"key":"e_1_2_7_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.05.009"},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21679"},{"key":"e_1_2_7_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/dac.612"},{"key":"e_1_2_7_15_1","doi-asserted-by":"crossref","unstructured":"MuraliS AtienzaD BeniniL De MichelG.A multi\u2010path routing strategy with guaranteed in\u2010order packet delivery and fault\u2010tolerance for networks on chip. In: Proceedings of the 43rd annual Design Automation Conference;2006;San Francisco CA.","DOI":"10.1145\/1146909.1147124"},{"key":"e_1_2_7_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2016.05.001"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.022"},{"key":"e_1_2_7_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.09.041"},{"key":"e_1_2_7_19_1","doi-asserted-by":"crossref","unstructured":"GratzP GrotB KecklerSW.Regional congestion awareness for load balance in networks\u2010on\u2010chip. Paper presented at: IEEE 14th International Symposium on High Performance Computer Architecture;2008;Salt Lake City UT.","DOI":"10.1109\/HPCA.2008.4658640"},{"key":"e_1_2_7_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1183946"},{"key":"e_1_2_7_21_1","unstructured":"HuJ MarculescuR.Exploiting the routing flexibility for energy\/performance aware mapping of regular NoC architectures. Paper presented at: Design Automation and Test in Europe Conference and Exhibition;2003;Munich Germany."},{"key":"e_1_2_7_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040204"},{"key":"e_1_2_7_23_1","unstructured":"BhandariR.Optimal diverse routing in telecommunication fiber networks. In: Proceedings of INFOCOM'94 Conference on Computer Communications;1994;Toronto Canada."},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140209"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90024-7"},{"issue":"4","key":"e_1_2_7_26_1","doi-asserted-by":"crossref","first-page":"303","DOI":"10.3233\/HSN-2001-208","article-title":"Survivability of lightwave networks\u2010path lengths in WDM protection scheme","volume":"10","author":"Sen A","year":"2001","journal-title":"J High Speed Netw"},{"key":"e_1_2_7_27_1","unstructured":"KarK KodialamM LakshmanTV.Routing restorable bandwidth guaranteed connections using maximum 2\u2010route flows. In: Proceedings of the Twenty\u2010First Annual Joint Conference of the IEEE Computer and Communications Societies;2002;New York NY."},{"key":"e_1_2_7_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2002.1007411"},{"key":"e_1_2_7_29_1","unstructured":"LiangW.Robust routing in wide\u2010area WDM networks. In: Proceedings of the 15th International Parallel and Distributed Processing Symposium;2001;San Francisco CA."},{"key":"e_1_2_7_30_1","unstructured":"ShaikhSZ.Span\u2010disjoint paths for physical diversity in networks. In: Proceedings of the IEEE Symposium on Computers and Communications;1995;Alexandria Egypt."},{"issue":"2","key":"e_1_2_7_31_1","first-page":"402","article-title":"Improving real\u2010time data dissemination performance by multi path data scheduling in data grids","volume":"34","author":"Atanak MM","year":"2015","journal-title":"Comput Inform"},{"issue":"2","key":"e_1_2_7_32_1","first-page":"737","article-title":"Resilient routing in optical networks using SRLG\u2010disjoint path pairs of min\u2010sum cost","volume":"52","author":"Gomes T","year":"2013","journal-title":"Telecommun Syst"},{"key":"e_1_2_7_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21778"},{"key":"e_1_2_7_34_1","first-page":"5","article-title":"An algorithm for enumerating SRLG diverse path pairs","author":"Gomes T","year":"2010","journal-title":"J Telecommun Inf Technol"},{"key":"e_1_2_7_35_1","doi-asserted-by":"crossref","unstructured":"RameyC.Tile\u2010Gx100 Manycore Processor: Acceleration interfaces and architecture. Paper presented at: IEEE Hot Chips 23 Symposium;2011;Stanford CA.","DOI":"10.1109\/HOTCHIPS.2011.7477491"}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4799","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T10:17:34Z","timestamp":1751797054000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,14]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,10]]}},"alternative-id":["10.1002\/cpe.4799"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4799","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"type":"print","value":"1532-0626"},{"type":"electronic","value":"1532-0634"}],"subject":[],"published":{"date-parts":[[2018,8,14]]},"assertion":[{"value":"2018-03-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e4799"}}