{"entities":{"Q1105496":{"pageid":1116245,"ns":120,"title":"Item:Q1105496","lastrevid":66142221,"modified":"2026-04-12T07:50:01Z","type":"item","id":"Q1105496","labels":{"en":{"language":"en","value":"On common edges in optimal solutions to traveling salesman and other optimization problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4059144"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$5AA942E3-3B76-47E2-8FC8-AF2D3B6DABFB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5f5991882dd9f170c27625a1e34be03f97c829af","datavalue":{"value":{"text":"On common edges in optimal solutions to traveling salesman and other optimization problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1105496$C3C0AFFA-493C-45FF-A74C-B3567E98A11C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a97e13b648cf53671d3da9a3dc4cb657d6455eba","datavalue":{"value":"0648.90082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105496$F9DB916E-6209-4A1F-9F45-F0EAE36C161C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5ffcd5b91577d60662c420532d875f4d3e276de5","datavalue":{"value":"10.1016/0166-218X(88)90057-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105496$8435D8E5-2CD1-476E-A272-0060B132374F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aedf720352fcca932fab3523c4bbcafd7c4c7cdb","datavalue":{"value":{"entity-type":"item","numeric-id":1104176,"id":"Q1104176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$D747B5C5-81C1-4B00-B87A-78A2190B6A27","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$1F6356DB-AD6A-4118-ACB3-54FCB87FA310","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1105496$0FC8B9DB-658C-41D0-9044-8E971F72E167","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"594e3681d0e316b100580d630ec25e257d79ca7f","datavalue":{"value":"Relationships between the symmetric traveling salesman problem (TSP), the minimum perfect matching problem (MPM) and the minimum spanning tree problem (MST), defined on a complete graph with n vertices where a cost is given for each edge, are explored. The main result shows that: if n is even, there exist optimal solutions to TSP and MPM which have at least two common edges; there exist optimal solutions to TSP and MST which have at least two common edges; and if n is even, there exist optimal solutions to MPM and MST which have at least one common edge. Problem instances are presented to demonstrate that these lower bounds on the number of common edges can be attained, thus proving that no stronger result is possible.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105496$535D51D5-C421-424B-89DC-2D3752F9B862","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e7c71cb6db7e3f55150cd62e2bbcf6bbc70b9472","datavalue":{"value":{"entity-type":"item","numeric-id":761339,"id":"Q761339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$332E4039-EDD4-4FCE-A6B4-48E91038E49D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105496$0BA0DF1E-99CE-498A-A323-F6C12BFF5EBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105496$D17E733B-E923-4F04-BE77-ECE218A9D928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105496$A957DC55-D18B-4207-A4DA-836C5E8235BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105496$E97DD59E-DBFF-4CA1-98A2-EC2B595ED17A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"32bf20b91d9777604f58731db2009ae4d1839651","datavalue":{"value":"4059144","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105496$98947C5C-8E4A-469C-8DBA-8B3EE504B74C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"380418f9694f7a498c4c86d6efdeb1edd87aac4b","datavalue":{"value":"symmetric traveling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105496$0CA407CF-555E-43D6-9595-7D5BB8DA237B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f32b9a39151b4b154aeaaa4d47028e266fb1cb87","datavalue":{"value":"minimum perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105496$0C8314F1-C4B6-41AD-B07D-C6EC524B5192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"732e1592c53acfd9740f2cb8680bbb91fda5b0af","datavalue":{"value":"minimum spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105496$306C04E0-B6D7-45B9-9A7C-C50552DF107C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f2bd7369831d9e54b4e511b9d71ba97d1e383ac","datavalue":{"value":"complete graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105496$983FD557-C409-4218-9F08-0DC1D8C8E0EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8bac01ad305f909bae8cd98ca0c6610245170ac","datavalue":{"value":"common edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105496$4DED88BC-7509-40A0-AA56-034E20C1C6E2","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$03257699-548B-4CD8-86F6-88A86D70CC6F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"af364193c4b41b4ead3ba5b26139af2dae8ec97d","datavalue":{"value":{"entity-type":"item","numeric-id":3912828,"id":"Q3912828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$D6A53CC2-30EE-412C-9229-70B3BDE7D0CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f50d2322f548fd02eddfc06ebc5035333ff03f3","datavalue":{"value":{"entity-type":"item","numeric-id":1076695,"id":"Q1076695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$332098AB-9F83-4B42-A8E7-863086ECB7EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$3E19122B-AFA9-42EE-8C9C-65C9AA580E51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$48FCA6B0-5F96-48BF-8B81-D32B694CE67B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4a96b78830b790348c79c4b0fb8e673b2a34afd","datavalue":{"value":{"entity-type":"item","numeric-id":3724370,"id":"Q3724370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$567C6C0B-AC32-4E82-B489-D57C41A3722B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1e8cd036db1b9a3cf0838006249f503381e192b","datavalue":{"value":{"entity-type":"item","numeric-id":1250225,"id":"Q1250225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$B47CB53B-D78D-48AB-83FE-EBF6F6B06D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$DACDD973-A2E3-4655-9D65-2D8FDF6504D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b5b903864765fb40a5b80f7f222eabf61ff3f0c","datavalue":{"value":{"entity-type":"item","numeric-id":5641007,"id":"Q5641007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$43D1AD21-829C-4749-9504-3D5FF9B4ED2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$35F2E4A0-40C6-44E6-BCDA-1FFF2C3A2D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f030d49769421de93ba4d8c53706308a5ef4c44c","datavalue":{"value":{"entity-type":"item","numeric-id":5187226,"id":"Q5187226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$2EBD63FB-6826-476F-A213-9D51D62D8757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b98ff2aab01c4bd8cfe081b2c02508c6cfb0548","datavalue":{"value":{"entity-type":"item","numeric-id":3959443,"id":"Q3959443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$7A9D2A82-0D3A-452E-8A50-7659F23912F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2a0e75602c9b8196c0f2a5f25247e3a2098384d","datavalue":{"value":{"entity-type":"item","numeric-id":4132556,"id":"Q4132556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$B4891356-FF6C-4028-A97F-FA72CE1318CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e689ca9104617943bd76b284824e0c9ceb6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3707420,"id":"Q3707420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$C0117739-E0F4-44E8-833D-D3D9950668DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3963223ca4d56ab1683b3c2d7b6d3c4a9f211a4e","datavalue":{"value":{"entity-type":"item","numeric-id":4161352,"id":"Q4161352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105496$F55CB0FE-0DDA-4502-90E8-F42CFFB2A47E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ba8dce51899d551c2b27b4950cf6131355fab0e","datavalue":{"value":{"entity-type":"item","numeric-id":1078097,"id":"Q1078097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f94d8c6ab456081d5577ac87bf6b84ff340caee","datavalue":{"value":{"amount":"+0.7345930337905884","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1105496$C67647BC-F225-4C66-ABBB-FE4F0D7ADFEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96f6731b252bf9da49501458669faace7cec8a41","datavalue":{"value":{"entity-type":"item","numeric-id":4845366,"id":"Q4845366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2443f0b813df687c50fd075ff1f7244f941ff720","datavalue":{"value":{"amount":"+0.7206397652626038","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1105496$01E88AC7-F8DF-4EB7-AD40-FCEE7968AF3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ebd2da6db20b822cbccc54045d3129603f48986","datavalue":{"value":{"entity-type":"item","numeric-id":5749151,"id":"Q5749151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2443f0b813df687c50fd075ff1f7244f941ff720","datavalue":{"value":{"amount":"+0.7206397652626038","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1105496$0A1D7B26-7C15-4EDD-A904-797D29B4A68D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25cd10b71b033c6631ca4c2351186610de0f15d4","datavalue":{"value":{"entity-type":"item","numeric-id":3337972,"id":"Q3337972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5968cb18d78a6f9de39e01ae0f7d0cc298128cce","datavalue":{"value":{"amount":"+0.7177814245223999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1105496$F2F4E2E3-A0CF-4251-AC8B-85FBD7EF7583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d39134cf7da67a247b51efbfb2c948ea13dd35b","datavalue":{"value":{"entity-type":"item","numeric-id":408370,"id":"Q408370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1798afa332c45e50d7c6b4e4163406ea205e495","datavalue":{"value":{"amount":"+0.7127880454063416","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1105496$020EE87F-73C2-4924-AEC5-951806A2B4EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On common edges in optimal solutions to traveling salesman and other optimization problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_common_edges_in_optimal_solutions_to_traveling_salesman_and_other_optimization_problems"}}}}}