{"entities":{"Q1382268":{"pageid":1393008,"ns":120,"title":"Item:Q1382268","lastrevid":67304625,"modified":"2026-04-12T16:43:34Z","type":"item","id":"Q1382268","labels":{"en":{"language":"en","value":"Better approximations of non-Hamiltonian graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1133164"}},"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":"Q1382268$5A1A533C-4553-49DF-8910-1A2C5FE6ED05","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"25b3ce46aaa4b4a6cdff7d8df557acc809f748f9","datavalue":{"value":{"text":"Better approximations of non-Hamiltonian graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1382268$1EAA8CA6-BF7E-4A95-8CEA-EB87C8C965C5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"19726b5b4ee51d0365d773dfa1d63a623e61b66a","datavalue":{"value":"0940.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382268$07E3B43F-BECA-40F8-AE88-3047F1A791E5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"28a3828d316b61e8b91bae8c5d057af415fd9b62","datavalue":{"value":"10.1016/S0166-218X(97)00099-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382268$1C68A00E-FE62-4885-B46D-CA413EDC49E0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"78a21800a31795763583b54b40324d17bf6c6658","datavalue":{"value":{"entity-type":"item","numeric-id":261377,"id":"Q261377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$09AEBF5F-7EF3-4737-A66F-789A35F9290E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"af43faa902926c77908e47b2c6b566ceec480768","datavalue":{"value":{"entity-type":"item","numeric-id":260258,"id":"Q260258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$92AB1647-A86C-4781-97F5-D5BFCB04A9AC","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":"Q1382268$659AACA5-100B-4460-BF7F-E5D65306DA2A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6fa0fec9b6972e0aceb387683cf418851ba7bbbf","datavalue":{"value":{"time":"+1998-06-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1382268$F25A76A1-1AED-47F3-BB69-BA0082A61256","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"26b42d6b95db34680d13ec2f1b8fe3a44fc40397","datavalue":{"value":"The problem of recognizing the class of non-sub-2-factor graphs (NS2F) is established to be NP-complete. Another proof of an earlier result about NP-ompleteness for the class of non-1-tough graphs (N1T) is also given. Both classes may have applications in generating, in polynomial time, random non-Hamiltonian graphs. In this paper it is argued that the class NS2F is substantially larger than the class N1T (the difference is a \\(\\text{D}^P\\)-complete set) and, thus, is more suitable for the task of random generation of instances of non-Hamiltonian graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382268$370F513E-4F96-48D2-965D-9A87AAB645E8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382268$8070AC94-D8B8-4CF7-9D09-904EC5E75F0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382268$AB446AA1-4E78-4CA5-8CD4-E2566C60A872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382268$03312598-0329-4A6E-BA83-52C4E41D2A8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382268$65B3DA63-A46A-498F-BC7B-3320290BB27F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382268$0874854B-9A14-4EDE-AAFE-57CCF2C830B2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0e2f97d534a371a7f80e0ef63cbc570c6ef20057","datavalue":{"value":"1133164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382268$E6096161-7CBB-4E07-9DEA-90CA926C5AD4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"942152a6cf2b636cb6c91b80d824f36dea0502e2","datavalue":{"value":"NP-ompleteness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382268$DDFF209C-30EE-485B-AD49-5D82B0D2C402","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59bc112e0f03e9f15cb61be87201c416a2cbe332","datavalue":{"value":"non-Hamiltonian graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382268$3B34298D-8D74-4B9A-B98F-3E15514FB206","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1066df8fa2473718870aa39fa75d20383df478d3","datavalue":{"value":{"entity-type":"item","numeric-id":286082,"id":"Q286082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$97484317-727E-402B-970A-C7D0150BA148","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":"Q1382268$10ECE322-9651-4AD1-9713-90109FF148B4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8efc2796cb38d8276b7b9b57e9267c43d63a9c6","datavalue":{"value":{"entity-type":"item","numeric-id":5687264,"id":"Q5687264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$C50622AC-8EFF-4A4E-9DA3-7B4FD16069DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"261b30465b2f9b97ed6391eb2fa761c1d658a808","datavalue":{"value":{"entity-type":"item","numeric-id":918697,"id":"Q918697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$6110B2EB-6FFB-4336-B4BB-F360917CAE5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c317ee9b89d25866849eff84487be5a7c7991b60","datavalue":{"value":{"entity-type":"item","numeric-id":3331209,"id":"Q3331209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$CB8BD4D9-3D14-4870-81C5-8558E144A6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2ca07d50aa240b4ccbe9fedf2b4516f9bba12f","datavalue":{"value":{"entity-type":"item","numeric-id":2558871,"id":"Q2558871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$C701EC10-E100-4C7E-9F81-FCB71546F5BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79b2cd01bd8642a86b4a476512521b17956a3210","datavalue":{"value":{"entity-type":"item","numeric-id":3689218,"id":"Q3689218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$36DF4A28-AB6E-4EB2-9CC6-3A3B28149AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5a384833facfee1bed7555c136a9c348cab3dd0","datavalue":{"value":{"entity-type":"item","numeric-id":5687266,"id":"Q5687266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$FCB2907A-B438-44B6-859F-9356687EDD63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8788f05ae82cfbd0ae01fb3681f4ca02a719c218","datavalue":{"value":{"entity-type":"item","numeric-id":3731636,"id":"Q3731636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$B8F75C91-88DA-4DB9-A605-A7BB18CD897D","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":"Q1382268$8337B524-89CA-45B9-A080-71C396EDC2F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01fc2040ffe16ed03fdd5700cb1de1e73a3cea54","datavalue":{"value":{"entity-type":"item","numeric-id":3787474,"id":"Q3787474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$9CDAE1C3-BE2C-4819-8303-4846A2413879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"800321fe9f6efe205a2eb283e0da5841a2b5eaad","datavalue":{"value":{"entity-type":"item","numeric-id":1061485,"id":"Q1061485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$10344367-2895-44B7-9783-0D93431E57C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ebf50b3b231b28dd36b98369bafa45d547ad97d","datavalue":{"value":{"entity-type":"item","numeric-id":1109565,"id":"Q1109565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$B350E2A3-77A0-42DF-83C9-753E69AF718D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce1a4cbf9349a81f7a149809f6ad7da5ffab291f","datavalue":{"value":{"entity-type":"item","numeric-id":1805463,"id":"Q1805463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382268$C29FA1E0-4813-4213-84ED-4AA7CD639843","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b1ab6aac0f49e05e25ec74633716b7a76849618b","datavalue":{"value":"Q128037044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382268$D1CD9E01-71E2-450D-8CE1-5D2BD4414B35","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1232a61caaa14b6ae706cb2ad4c7682e9fa5866d","datavalue":{"value":{"entity-type":"item","numeric-id":4604513,"id":"Q4604513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b92b2108220990354f1c03802d327a060c9f6f9b","datavalue":{"value":{"amount":"+0.9098102","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382268$D64778BD-2B6F-4D1F-B845-BED758A8759F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e811d1eca72c0c5642a91457b0b4bf435cfb7ffd","datavalue":{"value":{"entity-type":"item","numeric-id":5384040,"id":"Q5384040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fdeb8674b71aeaf68029ad55ead8d6c53203090","datavalue":{"value":{"amount":"+0.8925574","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382268$A6158E9C-8D1D-4AF4-9A14-3D90265F5AF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8b12cbd1f4e8ae37781c06447c13a257c0926b4","datavalue":{"value":{"entity-type":"item","numeric-id":4240135,"id":"Q4240135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65c4e5dd69b2c98f45c1ab616f55c9d29eadedd7","datavalue":{"value":{"amount":"+0.88382703","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382268$8CB0C26F-92CD-4477-B3C3-FFE57E4D0261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cf012dd8f45414000f367732a3edaa640355e43","datavalue":{"value":{"entity-type":"item","numeric-id":5954242,"id":"Q5954242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fa6dd2e3eed55a6599c61d00dd3a066147d7e7b","datavalue":{"value":{"amount":"+0.88215756","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382268$C5F02AAD-C2A3-46C0-B501-1B7A47D0BB1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa1491d4f766f61cdcf25bd6e69dab498944f931","datavalue":{"value":{"entity-type":"item","numeric-id":3356326,"id":"Q3356326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54909cd45538b9e346f10e213978f38054ef2a29","datavalue":{"value":{"amount":"+0.875134","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382268$917D1816-D4A9-495B-9657-EFB3A809AF9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00f53027330fb23518a5211388959ba2661a1707","datavalue":{"value":{"entity-type":"item","numeric-id":5757904,"id":"Q5757904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15ea475ab32963e063531098b93fb853e4f7daaf","datavalue":{"value":{"amount":"+0.87320745","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382268$632146C4-B423-4C62-8CE3-5B387E2DBC78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cd98d9cb4c4496e45b4a2ac1a21cd5b737c08b0","datavalue":{"value":{"entity-type":"item","numeric-id":5368902,"id":"Q5368902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afa93d50683fc6e222bae4fb34a7e99fa7b7ac1a","datavalue":{"value":{"amount":"+0.87166905","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382268$8F48342C-36A1-43AD-88F8-790192AC84CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1d6aac293b216566c9bd136f83ca9650fe1c5c9","datavalue":{"value":{"entity-type":"item","numeric-id":2851861,"id":"Q2851861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afa93d50683fc6e222bae4fb34a7e99fa7b7ac1a","datavalue":{"value":{"amount":"+0.87166905","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382268$86DE67E3-4FD3-42ED-9063-436A7092C994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eca1417ad51f1f874c7cda062a0dc2156112bb89","datavalue":{"value":{"entity-type":"item","numeric-id":3115248,"id":"Q3115248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"152aa22317fd9ac842e73c85c6c15cd2cf863f56","datavalue":{"value":{"amount":"+0.87045693","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382268$A7ED70EF-CDB1-4511-8D08-BC978A3FD2EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fa24af5e6826490b408991ce6a201d2162cbcc8","datavalue":{"value":{"entity-type":"item","numeric-id":2184681,"id":"Q2184681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08b5a30366fc8b689b2f2a54ce04c3c8f36e0be9","datavalue":{"value":{"amount":"+0.87027097","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382268$7BA14314-9F36-4B2D-9E17-FC81FD7AD701","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Better approximations of non-Hamiltonian graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Better_approximations_of_non-Hamiltonian_graphs"}}}}}