{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:49:36Z","timestamp":1757314176639},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,3,26]],"date-time":"2013-03-26T00:00:00Z","timestamp":1364256000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2015,2]]},"DOI":"10.1007\/s10878-013-9606-z","type":"journal-article","created":{"date-parts":[[2013,3,25]],"date-time":"2013-03-25T03:14:55Z","timestamp":1364181295000},"page":"433-450","source":"Crossref","is-referenced-by-count":2,"title":["A tolerance-based heuristic approach for the weighted independent set problem"],"prefix":"10.1007","volume":"29","author":[{"given":"B. I.","family":"Goldengorin","sequence":"first","affiliation":[]},{"given":"D. S.","family":"Malyshev","sequence":"additional","affiliation":[]},{"given":"P. M.","family":"Pardalos","sequence":"additional","affiliation":[]},{"given":"V. A.","family":"Zamaraev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,26]]},"reference":[{"key":"9606_CR1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1080\/10586458.2001.10504428","volume":"10","author":"W Aiello","year":"2000","unstructured":"Aiello W, Chung F, Lu L (2000) A random graph model for power-law graphs. Exp Math 10:53\u201366","journal-title":"Exp Math"},{"key":"9606_CR2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1287\/opre.39.1.150","volume":"39","author":"E Balas","year":"1991","unstructured":"Balas E, Saltzman M (1991) An algorithm for the three-index assignment problem. Oper Res 39:150\u2013161","journal-title":"Oper Res"},{"key":"9606_CR3","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A Barabasi","year":"1999","unstructured":"Barabasi A, Reka A (1999) Emergence of scaling in random networks. Science 286:509\u2013512","journal-title":"Science"},{"key":"9606_CR4","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/11427186_55","volume":"3503","author":"H Bekker","year":"2005","unstructured":"Bekker H, Braad E, Goldengorin B (2005) Selecting the roots of a small system of polynomial equations by tolerance based matching. Lect Notes Comput Sci 3503:610\u2013613","journal-title":"Lect Notes Comput Sci"},{"key":"9606_CR5","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron C, Kerbosch J (1973) Finding all cliques of an undirected graph. Commun ACM 16:575\u2013577","journal-title":"Commun ACM"},{"key":"9606_CR6","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1002\/rsa.1009","volume":"18","author":"B Bollobas","year":"2001","unstructured":"Bollobas B, Riordan R, Spencer J, Tusnady G (2001) The degree sequence of a scale-free random graph process. Random Struct Algorithms 18:279\u2013290","journal-title":"Random Struct Algorithms"},{"key":"9606_CR7","unstructured":"Boyko V, Goldengorin B, Kuzmenko V (2006) Tolerance-based algorithms. Theory Optim Decis 5:98\u2013104 (in Ukrainian)"},{"key":"9606_CR8","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF01934098","volume":"28","author":"C Chen","year":"1988","unstructured":"Chen C, Kuo M, Sheu J (1988) An optimal time algorithm for finding a maximum weight independent set in a tree. BIT Numer Math 28:353\u2013356","journal-title":"BIT Numer Math"},{"key":"9606_CR9","volume-title":"Introduction of algorithms","author":"T Cormen","year":"2001","unstructured":"Cormen T, Leiserson C, Rivest R, Stein C (2001) Introduction of algorithms, 2nd edn. MIT Press\/McGraw-Hill, Cambridge","edition":"2"},{"key":"9606_CR10","doi-asserted-by":"crossref","unstructured":"Ernst C, Dong C, Jager G, Richter D, Molitor P (2010) Finding good tours for huge euclidean TSP instances by iterative backbone contraction. In: AAIM, pp 119\u2013130","DOI":"10.1007\/978-3-642-14355-7_13"},{"key":"9606_CR11","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/316194.316229","volume":"29","author":"M Faloutsos","year":"1999","unstructured":"Faloutsos M, Faloutsos P, Faloutsos C (1999) On the power-law relationships of the internet topology. Comput Commun Rev 29:251\u2013262","journal-title":"Comput Commun Rev"},{"key":"9606_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-6103-3","volume-title":"Advances in sensitivity analysis and parametric programming","author":"T Gal","year":"1997","unstructured":"Gal T, Greenberg H (1997) Advances in sensitivity analysis and parametric programming. Kluwer Academic Publishers, New York"},{"key":"9606_CR13","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.cor.2011.04.003","volume":"39","author":"R Germs","year":"2012","unstructured":"Germs R, Goldengorin B, Turkensteen M (2012) Lower tolerance-based branch and bound algorithms for the ATSP. Comput Oper Res 39:291\u2013298","journal-title":"Comput Oper Res"},{"key":"9606_CR14","doi-asserted-by":"crossref","unstructured":"Ghosh D, Goldengorin B, Gutin G, Jager G (2007) Tolerance-based greedy algorithms for the traveling salesman problem. In: Bapat R, Das A, Partasaraty T, Neogy S (eds) Mathematical programming and game theory for decision making. World Scientific Publishing, Singapore","DOI":"10.1142\/9789812813220_0005"},{"key":"9606_CR15","doi-asserted-by":"crossref","first-page":"716","DOI":"10.3844\/jcssp.2006.716.734","volume":"2","author":"B Goldengorin","year":"2006","unstructured":"Goldengorin B, Jager G, Molitor P (2006) Tolerances applied in combinatorial optimization. J Comput Sci 2:716\u2013734","journal-title":"J Comput Sci"},{"key":"9606_CR16","doi-asserted-by":"crossref","unstructured":"Greenberg H (1998) An annotated bibliography for post-solution analysis in mixed integer and combinatorial optimization. In: Woodruff D (ed) Advances in computational and stochastic optimization, logic programming and heuristic search. Kluwer Academic Publishers, New York, pp 97\u2013148","DOI":"10.1007\/978-1-4757-2807-1_4"},{"key":"9606_CR17","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","volume":"126","author":"K Helsgaun","year":"2000","unstructured":"Helsgaun K (2000) An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur J Oper Res 126:106\u2013130","journal-title":"Eur J Oper Res"},{"key":"9606_CR18","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s12532-009-0004-6","volume":"1","author":"K Helsgaun","year":"2009","unstructured":"Helsgaun K (2009) General $$k$$ -opt submoves for the Lin-Kernighan TSP heuristic. Math Program Comput 1:119\u2013163","journal-title":"Math Program Comput"},{"key":"9606_CR19","doi-asserted-by":"crossref","unstructured":"Jager G, Molitor P (2008) Algorithms and experimental study for the traveling salesman problem of second order. In: COCOA, pp 211\u2013224","DOI":"10.1007\/978-3-540-85097-7_20"},{"issue":"1","key":"9606_CR20","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J Kruskal","year":"1956","unstructured":"Kruskal J (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7(1):48\u201350","journal-title":"Proc Am Math Soc"},{"key":"9606_CR21","doi-asserted-by":"crossref","first-page":"1481","DOI":"10.1016\/S1389-1286(99)00040-7","volume":"7","author":"R Kumar","year":"1999","unstructured":"Kumar R, Raghavan P, Rajagopalan S, Tomkins A (1999) Trawing the Web for emerging cyber-communities. Comput Netw 7:1481\u20131493","journal-title":"Comput Netw"},{"key":"9606_CR22","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1287\/opre.16.3.682","volume":"16","author":"K Murty","year":"1968","unstructured":"Murty K (1968) An algorithm for ranking all the assignments in order of increasing cost. Oper Res 16: 682\u2013687","journal-title":"Oper Res"},{"key":"9606_CR23","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s10107-004-0517-8","volume":"102","author":"R Ramaswamy","year":"2005","unstructured":"Ramaswamy R, Orlin J, Chakravarti N (2005) Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs. Math Program 102:355\u2013369","journal-title":"Math Program"},{"key":"9606_CR24","unstructured":"Reinfeld N, Vogel W (1965) Mathematical programming. Prentice Hall, Englewood Cliffs"},{"key":"9606_CR25","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/net.3230100402","volume":"10","author":"D Shier","year":"1980","unstructured":"Shier D, Witzgall C (1980) Arc tolerances in minimum-path and network flow problems. Networks 10: 277\u2013291","journal-title":"Networks"},{"key":"9606_CR26","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0166-218X(93)E0126-J","volume":"58","author":"Y Sotskov","year":"1995","unstructured":"Sotskov Y, Leontev V, Gordeev E (1995) Some concepts of stability analysis in combinatorial optimization. Discret Appl Math 58:169\u2013190","journal-title":"Discret Appl Math"},{"key":"9606_CR27","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/0020-0190(82)90137-5","volume":"14","author":"R Tarjan","year":"1982","unstructured":"Tarjan R (1982) Sensitivity analysis of minimum spanning trees and shortest path trees. Inf Process Lett 14:30\u201333","journal-title":"Inf Process Lett"},{"key":"9606_CR28","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1016\/j.ejor.2006.10.062","volume":"189","author":"M Turkensteen","year":"2008","unstructured":"Turkensteen M, Ghosh D, Goldengorin B, Sierksma G (2008) Tolerance-based branch and bound algorithms for the ATSP. Eur J Oper Res 189:775\u2013788","journal-title":"Eur J Oper Res"},{"key":"9606_CR29","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/S0305-0548(98)00070-7","volume":"26","author":"E Poort Van der","year":"1999","unstructured":"Van der Poort E, Libura M, Sierksma G, Van der Veen J (1999) Solving the $$k$$ -best traveling salesman problem. Comput Oper Res 26:409\u2013425","journal-title":"Comput Oper Res"},{"key":"9606_CR30","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1016\/j.ejor.2004.09.015","volume":"169","author":"A Volgenant","year":"2006","unstructured":"Volgenant A (2006) An addendum on sensitivity analysis of the optimal assignment. Eur J Oper Res 169:338\u2013339","journal-title":"Eur J Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9606-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-013-9606-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9606-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,11]],"date-time":"2019-07-11T09:14:04Z","timestamp":1562836444000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-013-9606-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,26]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["9606"],"URL":"https:\/\/doi.org\/10.1007\/s10878-013-9606-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,26]]}}}