{"entities":{"Q1197026":{"pageid":1207775,"ns":120,"title":"Item:Q1197026","lastrevid":66338727,"modified":"2026-04-12T09:26:05Z","type":"item","id":"Q1197026","labels":{"en":{"language":"en","value":"An extension of the multi-path algorithm for finding Hamilton cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 89901"}},"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":"Q1197026$198BA0F4-6432-4F3F-889E-ED11EF2874C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef728703596df2182bdc6990653259fe259d79e9","datavalue":{"value":{"text":"An extension of the multi-path algorithm for finding Hamilton cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1197026$F4E3BEC2-85C1-4D3E-A9A6-23570E9CD96B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b99d39a469fbed633d0eb98dc03b763ce02ad83f","datavalue":{"value":"0761.05088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197026$EACA520A-E9BE-4430-9E0A-539C52A8D720","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8fc2d823cf0c7ab856760206e0f3dc595c7d18d7","datavalue":{"value":"10.1016/0012-365X(92)90601-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197026$4842AD10-5422-44AF-8938-512D23425F75","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197026$E96C253F-7063-4A3A-A147-5A0B5D9FE346","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1197026$3C26F94F-CE04-41BF-BADD-487464DF3584","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2b2d7245f3d1ad7fd8c043063add5485670dc45a","datavalue":{"value":"Chistofides described the multi-path algorithm for finding Hamilton cycles in a graph \\(G\\). This algorithm is an intelligent exhaustive search for a Hamilton cycle. The author describes how this algorithm can be modified. He gives two ways for improving: (1) by detecting small separating sets \\(M\\) for which \\(G-M\\) has more than \\(| M|\\) components; and (2) by detecting bipartitions \\((X,Y)\\) with \\(| X|<| Y|\\). These conditions enable the algorithm to recognize, in certain cases, that \\(G\\) is non-Hamiltonian. The modifications are described in a pseudo-language.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197026$ADB82B13-8820-4342-9713-9C359AC78737","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bee1f7445f48f88ea32c13733d6b7ad82b5d2674","datavalue":{"value":{"entity-type":"item","numeric-id":803176,"id":"Q803176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197026$2A4BBB2A-80C3-42EC-A691-E15993F07601","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197026$F11AA22C-372C-4740-A11F-91C589758905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197026$31F20AEF-8542-433C-BB0F-91DAA5A93136","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5dee6b5c975457ac55d551a202e76406d40baa3b","datavalue":{"value":"89901","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197026$7D9F5631-3997-49AC-A562-AF3AF15D1769","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e08bbadc7d3113a27560f3cb724d9d464dde3414","datavalue":{"value":"multi-path algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197026$89F0976B-2EC5-4FF2-B30A-BEE0485D7DDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c51a5f2b554ad725199c724ddbac3b61a9fd8af1","datavalue":{"value":"Hamilton cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197026$F319647A-3832-4648-9D05-E8ED4AA0EDCE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e2966ef99caf6a8eebfa185ead073bf0f08f6c5","datavalue":{"value":{"entity-type":"item","numeric-id":343750,"id":"Q343750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197026$0C176464-2794-4B9C-9DB6-D42DED387828","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":"Q1197026$2351025D-C9CF-4264-BC00-B621BBC3608B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197026$5538E303-4B9F-4E3F-9C76-AEBFE56F53A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197026$669722C6-8E16-413B-803A-D4B87122B7DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab4410bd85ba93ca8638378f859367903f5b9ff0","datavalue":{"value":{"entity-type":"item","numeric-id":4083324,"id":"Q4083324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197026$B0F6BAC4-AB85-4145-9EFE-37873D601D65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e93fcc5f5e8911813f16fcd1e3e08e519d9e013","datavalue":{"value":{"entity-type":"item","numeric-id":4767335,"id":"Q4767335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197026$4596DA56-6C38-4CE9-BC9A-B9CF47ACC6BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daa748eaf541ef47b9bc5728b38f8d3e305bac1d","datavalue":{"value":{"entity-type":"item","numeric-id":4044618,"id":"Q4044618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197026$7E927751-88A2-4148-A088-3AAED7B9E353","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab905d27922a85af616443e1769a1850cb9248b6","datavalue":{"value":{"entity-type":"item","numeric-id":5524326,"id":"Q5524326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197026$EC16A24F-F963-4C79-B01C-B7F6C3DFBE3B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5b97d24b8ff7d8ee3b4d1815349597e2cb40e88","datavalue":{"value":{"entity-type":"item","numeric-id":2963159,"id":"Q2963159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5eaaf6a9bc756fc7e1efffaa40114752a544dcdb","datavalue":{"value":{"amount":"+0.840794026851654","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":"Q1197026$36DFAC8A-97E7-4F5A-BB39-F7A694663FF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ceabe4942b2e51efcb390b534644893f9f753a24","datavalue":{"value":{"entity-type":"item","numeric-id":1099190,"id":"Q1099190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23c13850a7786ba2e106f74834b76c402778efc9","datavalue":{"value":{"amount":"+0.788249135017395","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":"Q1197026$D346D1ED-5602-4F99-915D-ABA082F54CC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ec5cdb1ac29996d9514baf9471615dc71ad20d7","datavalue":{"value":{"entity-type":"item","numeric-id":5475257,"id":"Q5475257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bef27a760b084e4b6192611699f5a3aa360d877","datavalue":{"value":{"amount":"+0.7644837498664856","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":"Q1197026$C6775759-9C60-4002-9259-E26C6A712E25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed25ca31f624ec9eb4c7195f2fb5cae0aaf68fef","datavalue":{"value":{"entity-type":"item","numeric-id":3689218,"id":"Q3689218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed876a23a463b8bf5cbf1630b4988df8ac6f749d","datavalue":{"value":{"amount":"+0.7527143955230713","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":"Q1197026$67C7CC4F-AAE6-47E5-A27A-CA25820893A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26ee60615e9604043b25cd52b722cff3e92cb917","datavalue":{"value":{"entity-type":"item","numeric-id":4306372,"id":"Q4306372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"351ddc0b7358c88b7cabb3a3f33871e1d6d1a30f","datavalue":{"value":{"amount":"+0.7423844337463379","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":"Q1197026$019D5C73-9A8C-4363-BC92-3C60C82744D0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An extension of the multi-path algorithm for finding Hamilton cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_extension_of_the_multi-path_algorithm_for_finding_Hamilton_cycles"}}}}}