{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T16:57:51Z","timestamp":1790441871793,"version":"4.1.0"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"publisher","award":["DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-AC02-05CH11231"]}],"id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>In 2017 Pichon et al. introduced an effective method for reordering columns within supernodes based on reformulating the underlying optimization problem as a set of traveling salesman problems (TSPs), one for each supernode. The primary problem with their approach is its cost in time, and the primary bottleneck is computing the TSP distances. We introduce techniques that dramatically reduce the time required by their method. First, we introduce a straightforward technique for reducing the size of a TSP, thereby reducing the number of TSP distances that must be computed and also reducing the cost of computing the TSP tour afterward. Second, we introduce a more complex and efficient algorithm for computing the TSP distances that exploits the fact that the relevant sets induce subtrees in the supernodal elimination tree. (A corrected version is attached.)<\/jats:p>","DOI":"10.1137\/20m1368070","type":"journal-article","created":{"date-parts":[[2021,9,7]],"date-time":"2021-09-07T10:30:01Z","timestamp":1631010601000},"page":"1337-1364","source":"Crossref","is-referenced-by-count":1,"title":["Fast Implementation of the Traveling-Salesman-Problem Method for Reordering Columns within Supernodes"],"prefix":"10.1137","volume":"42","author":[{"given":"Mathias","family":"Jacquelin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Esmond G.","family":"Ng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barry W.","family":"Peyton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,9,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894278952"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/0916081"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/76909.76910"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1177\/109434208700100403"},{"key":"atypb5","first-page":"1","author":"Blair J. R. S.","year":"1993","journal-title":"New York"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"atypb8","unstructured":"A. George and J. W. H. Liu,\n                      Computer Solution of Large Sparse Positive Definite Systems\n                      , Prentice-Hall, Englewood Cliffs, NJ, 1981."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/1031001"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/0715006"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892236921"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/090757216"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"M. Jacquelin, E. G. Ng, and B. W. Peyton,\n                      Fast and effective reordering of columns within supernodes using partition refinement\n                      , in Proceedings of the 8th SIAM Workshop on Combinatorial Scientific Computing, 2018, pp. 76-86.","DOI":"10.1137\/1.9781611975215.8"},{"key":"atypb14","first-page":"215","author":"Johnson D. S.","year":"1997","journal-title":"UK"},{"key":"atypb15","first-page":"85","author":"Karp R. M.","year":"1972","journal-title":"New York"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/214392.214398"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/6497.6499"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/0611010"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/0614019"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/0216062"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/16M1062454"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(70)90282-9"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/0206041"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1967.6011"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1368070","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:51:05Z","timestamp":1787334665000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1368070"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1368070"],"URL":"https:\/\/doi.org\/10.1137\/20m1368070","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}