{"entities":{"Q1302144":{"pageid":1312894,"ns":120,"title":"Item:Q1302144","lastrevid":70101051,"modified":"2026-04-13T12:26:59Z","type":"item","id":"Q1302144","labels":{"en":{"language":"en","value":"On the complexity of hamiltonian path and cycle problems in certain classes of digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1340625"}},"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":"Q1302144$D7D187B0-E678-40BE-8E60-59ABFBC40537","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"10186beee32cd949468dc41e0ef33c77a89c449d","datavalue":{"value":{"text":"On the complexity of hamiltonian path and cycle problems in certain classes of digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1302144$18B41DC1-F91B-45D9-9679-1DB8C29B41AB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"95cd168ae3fc5f9648d74ccf1bbed8ed0e0dba1f","datavalue":{"value":"0934.05082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$39370557-32DD-405D-B3C9-BF910D92ED0B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e30fd43d15a28f76ccb5efbc309e76d1671c257f","datavalue":{"value":"10.1016/S0166-218X(99)00064-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$FBA02A0D-FC2F-464B-AF5B-E27BB79FDBC6","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":"Q1302144$7803983C-646A-49BF-9FA8-175DE3F48AC5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3d7fcc00a8ca0e7d2bba3b2e6904026043bd3d23","datavalue":{"value":{"time":"+2000-04-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1302144$0F6317D3-7130-40DF-82AF-3582BF5D5022","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"90c4bcbcda7cde5266803fea14de20063c7b61b1","datavalue":{"value":"This is the most comprehensive and updated survey article with very detailed information and discussion about results on sequential and parallel complexity of hamiltonian problems for various classes of directed graphs that generalize tournaments (such as, locally in-semicomplete digraphs, semicomplete multipartite digraphs, path-mergeable digraphs, quasi-transitive digraphs, etc.). A few new results about hamiltonian path starting at a given vertex for some digraphs are also proved in this paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302144$777DC38B-58DF-47D5-8EA4-7C34A0CC7BC5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$32A6854A-71D1-4897-855D-3207C95773E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5106252eb72617afc052c075699a4fbf786bbc66","datavalue":{"value":"05-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$C030B495-15CE-404B-B9CF-00384A678574","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$B6E35751-1E87-4536-A7CA-8AAC48465AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$DB1A7EFA-6821-4D62-A4BD-A5B124877FE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$DE4D4BA7-5560-45DF-B0F0-5CCFDA1BA1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$EF1DC87D-4812-41A4-B210-10A8468D76B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$EB6A882F-471B-47E0-96FF-D9570B5D31C4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea9328d888965612c550c55f1b478f2adc4670eb","datavalue":{"value":"1340625","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$C769F7D0-9799-4582-8974-F881B06A64F4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"103dcccb1f4f4c672334af018c88096d1b765e96","datavalue":{"value":"Hamilton path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302144$E5822E98-3CAD-47ED-9499-C61EC22F9345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"579172068de96f7207eab70f6ed34d3150cd4308","datavalue":{"value":"Hamilton cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302144$911D224B-3FEB-4BD2-9978-F32E631C6B2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302144$CBEF45CC-974F-469C-B6FB-8B5AA4EFE38C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302144$E6350C22-D2E4-452A-B67B-F0B3F9B7A2FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2312ec23605fa0af9c2124d6c79ac4c6ccd84a22","datavalue":{"value":"tournament locally in-semicomplete digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302144$DFA22F02-48CE-41FB-8525-64761D1C1565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"696c86e7c8ae25d013e1baf92316ca662151659c","datavalue":{"value":"semicomplete multipartite digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302144$F4BC7C7F-17E8-440F-AC20-230AC8C25921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8cea6f69939eb65d71754f3eadf2ec6caf5eeaeb","datavalue":{"value":"path-mergeable digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302144$7F4B645F-28FE-40E3-B8DA-D985A999CA1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f688cd98dd590a02625b7e81dfc4b75b58aa7e59","datavalue":{"value":"quasi-transitive digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302144$4BD24212-59CB-4E63-A60B-E9701BD894DB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f64c4b091272c660c279938fc740575735afef58","datavalue":{"value":{"entity-type":"item","numeric-id":558237,"id":"Q558237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1302144$E9A0D2DA-C858-474B-AE2D-7A951261A1F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d62d1b98a8e47330bd8d09b4c364147d7b3d1f6","datavalue":{"value":{"entity-type":"item","numeric-id":168084,"id":"Q168084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1302144$7253C38B-82CF-42EF-BCDC-804A6687A80B","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":"Q1302144$FE478D77-7C67-4B69-A83F-75276C0529D6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"75173efd8234f4c6752ba90721b8a4275fe4219b","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00064-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1302144$889115A7-3903-4995-96A5-A459DD273C77","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cf59264ce073b4c0a18584273d8be1c767962f98","datavalue":{"value":"W1984883238","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$61B86EB8-2A9C-4A28-AA60-F1DBD763A052","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5c6809778d5d9060436378f25aebe658c7ea962d","datavalue":{"value":"Q128066106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302144$F0359C1B-4ED6-47C1-9CBE-1D1BA8688D59","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98841ab995efd7c33a8f1bb9b5c0ce1554195dab","datavalue":{"value":{"entity-type":"item","numeric-id":3978362,"id":"Q3978362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d40384dbe8505ab17876864fa77526bbd76a21fe","datavalue":{"value":{"amount":"+0.8246957063674927","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":"Q1302144$3ED7015D-CD36-41B4-87FC-D0358FF8C4A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34dfc806d1edfa9b66497cd17d88bd468ce70ccb","datavalue":{"value":{"entity-type":"item","numeric-id":1396651,"id":"Q1396651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62881f448cff6f2fd2b2a99eb2b97f79056dd7a0","datavalue":{"value":{"amount":"+0.8228951096534729","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":"Q1302144$691E0183-0AC8-4110-80B8-43E101384FDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08b69a43dcd1d6b96ea96c5a829f7c99a640a719","datavalue":{"value":{"entity-type":"item","numeric-id":2365177,"id":"Q2365177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d422b447c48fb5714e64f065d3013703231c8984","datavalue":{"value":{"amount":"+0.7939968705177307","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":"Q1302144$545AD1CA-0D30-4D7B-A88A-A0B986BC4F56","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of hamiltonian path and cycle problems in certain classes of digraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_hamiltonian_path_and_cycle_problems_in_certain_classes_of_digraphs"}}}}}